Алгоритмите често са трудни за разбиране от хората. Вярвам, че това е така, защото те най-често са програмирани или обяснени на език, който насърчава мисленето в процедури или инструкции, които не са интуитивни.

Много често същността на даден алгоритъм (как решавате определен проблем логически без компютърно кодиране) изглежда много проста и разбираема, когато е описана графично. Изненадващо обаче, често не се превежда добре в код, написан на езици като Python, Java или C++. Следователно става много по-трудно за разбиране.

С други думи, алгоритмичната концепция не се свързва директно с начина, по който кодът трябва да бъде написан и прочетен.

Защо алгоритмите са толкова трудни за кодиране?

Е, можем да обвиним за това вътрешната работа на ранните електромеханични компютри. Първите изобретатели на някои от най-използваните езици за програмиране днес никога не са могли да се отърват от тези функции. Или може би не са могли да не оставят пръстовите си отпечатъци върху изобретенията си. След като разберете компютрите толкова добре, няма как да отмените това.

За да влошат нещата, освен езиците за микро-управление, някой трябваше да изобрети API за по-добро микро-управление. Те го нарекоха обектно-ориентирано програмиране (ООП) и добавиха концепцията за класове към програмирането - но мисля, че модулите и функциите могат да се справят добре със същите неща, благодаря ви много.

C++ не направи C по-добър, но проправи път, като вдъхнови повече наследници на ООП. И всички заедно, всички тези неща затрудняват абстрактното алгоритмично мислене поради гореспоменатите причини.

Казусът: сортиране чрез сливане

За нашата дискусия ще използваме алгоритъм за сортиране чрез сливане като образец. Разгледайте диаграмата по-долу. Ако можете да броите и сглобявате пъзели, вероятно ще разберете как работи за няколко минути.

Ключовите стъпки за създаване на сортиране чрез сливане са няколко и прости. Всъщност мога да го обясня с помощта на цифровите блокове на дъщеря ми (полезно е да ги следвате, като се върнете към анимираната диаграма за справка):

  • Първо, трябва да продължим да разделяме списък с числа (или букви, или какъвто и да е тип сортируеми стойности) наполовина, докато завършим с много списъци с един елемент. Списък с един елемент е технически сортиран. Това се нарича тривиално сортирано.
  • След това създаваме нов празен списък, в който можем да започнем да пренареждаме елементите и да ги поставяме един по един според това кой е по-малък/по-малък от другия.
  • След това трябва да „слеем“ всяка двойка списъци обратно заедно, ефективно обръщайки стъпките на подразделяне. Но този път, на всяка стъпка от пътя, трябва да се уверим, че по-малкият елемент във въпросната двойка е поставен първи в празния списък.

В името на аргумента ще се опитаме да начертаем горните процеси, като направим всеки един подпрограма (функция в нормален говор). Най-простата част от този алгоритъм е сливането, така че нека първо започнем с това.

def merge(a, b):
    out = []
    while (len(a) > 0 and len(b) > 0): 
        if (a[0] <= b[0]):
            out.append(a[0])
            del a[0]
        else:
            out.append(b[0])
            del b[0]
    while (len(a) > 0):
        out.append(a[0])
        del a[0]
    while (len(b) > 0):
        out.append(b[0])
        del b[0]
    return out

Продължете и прекарайте известно време в разглеждането му. Може да забележите, че с императивния код на Python той е проектиран да бъде изричан и след това разбран. На английски е много разбираемо, но не и на логика.

Първият ни опит

Ето един опит (който евентуално бихте могли да използвате в сесия на бяла дъска):

За да обединим списък a и b, ще трябва първо да създадем празен списък с име out за по-голяма яснота (защото в Python не можем да сме сигурни, че той наистина ще бъде „излязъл“ накрая). След това, докато (или докато) и двата списъка не са празни, ще продължим да поставяме главата на двата списъка в битка. Който е по-малък или равен на опонента, печели и може да въведе out първи. Губещият ще трябва да остане и да чака там новия състезател по линията. Реваншите продължават до прекъсване на първия while цикъл.

Сега в даден момент или a, или b ще бъдат празни, оставяйки другия с един или повече висящи елемента. Без да останат състезатели в другия списък, двата цикъла while гарантират бързото проследяване на тези лоши елементи в out, така че и двата списъка да са изчерпани. След това, когато всичко е готово, връщаме out.

И това са тестовите случаи за сливане:

assert(merge([1], [2]) == [1, 2])
assert(merge([2], [1]) == [1, 2])
assert(merge([4, 1], [3, 0, 2]) == [3, 0, 2, 4, 1])

Надявам се в този момент да ви е ясно защо накрая получаваме резултата в последния случай. Ако не е, опитайте да нарисувате върху бяла дъска или лист хартия и да симулирате обяснението.

Разделяй и владей

Сега ще продължим с частта за подразделение. Този процес е известен още като разделяне или, на малко по-велик език, "Разделяй и владей" (между другото, "определението в политиката е също толкова интересно").

По принцип, ако нещо е трудно за завладяване или разбиране, трябва да го разбиете, докато стане по-малко и по-лесно за разбиране. Правете това, докато частите станат нечупливи и повторете процеса с останалите.

def half(arr):
    mid = len(arr) / 2
    return arr[:mid], arr[mid:]

Това, което прави рутината half, е да намери средния индекс, да раздели входния списък на приблизително равни подсписъци и да върне и двата като двойка. Трябва да направи това само веднъж, тъй като родителската функция в крайна сметка ще го извика рекурсивно.

Тъй като имаме частите, сега просто трябва да ги съберем в последователна схема. Това е мястото, където водата става мътна, защото са включени рекурсии.

Преди да навляза в повече код, позволете ми да обясня защо рекурсиите и императивните езици за програмиране като Python не си пасват толкова добре. Няма да навлизам в темата за оптимизацията, защото това не засяга днешната дискусия и не е толкова интересно.

Една отличителна ирония тук е, че дори в език с итеративни цикли като Python, той все още не може напълно да избегне рекурсията (може да се размине без рекурсия, но съм сигурен, че това би го направило още по-странно). Рекурсията е територия, където итеративните конструкции, като цикли for и while, стават напълно безполезни.

Освен това рекурсията не е естествена в Python. Не се чувства естествено и прозрачно, а по-скоро се усеща доста полуизпечено, както е неговата ламбда. Опитът за изразяване на рекурсии в Python би бил като: „Тогава правим това рекурсивно и просто се молим всичко да работи и да достигне основния случай в крайна сметка, така че да не се превърне в спирала в безкрайната тъмнина на препълването на стека“. Уау, нали?

И така, ето функцията mergesort:

def mergesort(arr):
    if (len(arr) <= 1):
        return arr
    left, right = half(arr)
    L = mergesort(left)
    R = mergesort(right)
    return merge(L, R)

Очевидно това е наистина чисто и лесно за четене. Но не е ясно какво се случва след извикването на half, поне семантично. Поради това „неприсъствие“ на рекурсията, рекурсивните извиквания са много непрозрачни и пречат на образователните усилия.

Единственият начин да визуализирате този процес на сортиране чрез сливане вероятно е да проследите промените в подсписъците във всяка стъпка:

input: [0, 3, 1, 3, 2, 6, 5]
A alias for mergesort / half
B alias for merge
## subdividing by half ...
                 A([0, 3, 1, 3, 2, 6, 5])
              A([0, 3, 1])    A([3, 2, 6, 5])
          A([0])  A([3, 1])  A([3, 2])   A([6, 5])
    A([]) A([0]) A([3])  A([1]) A([3]) A([2]) A([6]) A([5]) 
## base case reached, start merging ...
        
       B([], [0]) B([3], [1]) B([3], [2]) B([6], [5])
          B([0], [1, 3])         B([2, 3], [5, 6])
                B([0, 1, 3], [2, 3, 5, 6])
                 B([0, 1, 2, 3, 3, 5, 6])
output: [0, 1, 2, 3, 3, 5, 6]

Като асимптотична странична бележка, разделянето и завладяването почти винаги води до логаритмично време на изпълнение. Когато продължавате да разделяте колекция на N подколекции, независимо дали съдържа 10 или 100 000 000 елемента, броят на стъпките, предприети във втория случай, се увеличава със скоростта на лог база N.

Например, необходими са около 3 стъпки, за да продължите да делите 10 на 2, докато се доближи възможно най-близо до 1 (или точно 3 стъпки, за да достигнете 1 при целочислено деление). Но са необходими само около 26 стъпки, за да направите същото и да разделите 100 000 000 на 2, докато стигнете до 1. Този факт може да се изрази по следния начин:

2^3.321928 = 10
2^6.643856 = 100
...
2^26.575425 = 100000000
or 
log base 2 of 100000000 = 26.575425

Изводът тук е, че трябваше да визуализираме рекурсивните процеси, за да разберем вътрешната работа на алгоритъма - въпреки че изглеждаше толкова тривиално в анимираната диаграма.

Защо има разделение между концептуалните процеси на самия алгоритъм и кода, който инструктира компютъра да изчисли такива процеси?

Това е така, защото по някакъв начин, използвайки императивни езици, ние всъщност все още сме психически поробени от машините.

Гмуркане по-дълбоко в кода

"Има разлика между познаването на пътя и вървенето по него."
― Морфей, Матрицата

Програмирането е трудно, всички знаем това. А разбирането на програмирането по наистина задълбочен начин е още по-трудно за душата ви (и за кариерата ви). Но бих казал, че както каза Морфей, понякога всичко, което има значение, е да вървиш по пътя. Да можеш да виждаш ясно е едно от най-възнаграждаващите неща в програмирането.

Във функционалното програмиране програмистът (вие) заема предната позиция, за да види как данните се променят рекурсивно. Това означава, че имате способността да решите как данните от даден формуляр да се трансформират в данните от друг въз основа на моментната снимка на това как изглежда. Това не е различно от начина, по който сме визуализирали процеса на сортиране чрез сливане. Нека ви дам преглед.

Да приемем, че искате да създадете базов случай в Python. В него искате да върнете въпросния списък, когато има само един елемент, и празен списък, когато има два елемента. Така че трябва да напишете нещо подобно:

if (len(arr) == 1):
    return arr
elif (len(arr) == 2):
    return []

Или за да направите това по-лошо, но по-интересно, можете да опитате да получите достъп до първия елемент чрез индекс 0 и втория елемент чрез индекс 1 и да се подготвите да обработите IndexError изключение.

Във функционален език като Erlang - който ще използвам в тази статия за неговата система с динамичен тип като Python - вие повече или по-малко бихте направили нещо подобно:

case Arr of
  [_] -> Arr;
  [_,_] -> []
end.

Това ви дава по-ясна представа за състоянието на данните. След като бъде обучен достатъчно, той изисква много по-малко когнитивна сила, за да прочете и разбере какво прави кодът, отколкото len(arr). Само имайте предвид: програмист, който не говори английски, може да попита „какво е len?“ След това се разсейвате от буквалното значение на функцията вместо от стойността на този израз.

Това обаче си има цена: нямате лукса на циклична конструкция. Език като Erlang е естествен за рекурсия. Почти всяка смислена Erlang програма ще използва строги рекурсивни извиквания на функции. И затова се съпоставя по-тясно с алгоритмичните концепции, които обикновено се състоят от рекурсия.

Нека се опитаме да проследим отново нашите стъпки в създаването на mergesort, но този път в Erlang, като започнем с функцията merge.

merge([], [], Acc) -> Acc;
merge([], [H | T], Acc) -> [H | merge([], T, Acc)];
merge([H | T], [], Acc) -> [H | merge(T, [], Acc)];
merge([Ha | Ta], [Hb | Tb], Acc) ->
  case Ha =< Hb of
    true  -> [Ha | merge(Ta, [Hb | Tb], Acc)];
    false -> [Hb | merge([Ha | Ta], Tb, Acc)]
  end.

Каква мерзост! Определено не е подобрение по отношение на четливостта, мислите. Да, Erlang разбира се няма да спечели никакви награди за красив език. Всъщност много функционални езици могат да изглеждат като безсмислици за нетренираните очи.

Но нека му дадем шанс. Ще преминем през всяка стъпка, както сме правили преди, и може би накрая някои от нас ще видят светлината. Но преди да продължим, за тези от вас, които не са запознати с Erlang, това са някои точки, които си струва да се отбележат:

  • Всеки блок от merge се счита за функционална клауза на същата функция. Те са разделени с ;. Когато израз завършва на Erlang, той завършва с точка (.). Това е конвенция за разделяне на функция на няколко клаузи за различни случаи. Например, клауза merge([], [], Acc) -> Acc; преобразува случая, когато първите два аргумента са празни списъци със стойността на последния аргумент.
  • Arity играе важна роля в Erlang. Две функции с едно и също име и арност се считат за една и съща функция. В противен случай те не са. Например merge/1 и merge/3 (как функциите и тяхната арност се адресират в Erlang) са две различни функции.
  • Erlang използва стриктно „съвпадение на шаблони“ (това се използва в много други функционални езици, но особено в Erlang). Тъй като стойностите в чистите функционални езици са неизменни, е безопасно да се обвържат променливи в подобна форма на данни към съществуващата със съвпадаща форма. Ето един тривиален пример:
{X, Y} = {0.5, 0.13}.
X.  %% 0.5
Y.  %% 0.13
[A, B, C | _] = [alice, jane, bob, kent, ollie].
[A, B, C].  %% [alice, jane, bob]
  • Обърнете внимание, че рядко ще говорим за връщане на стойности, когато работим с Erlang функции, защото те всъщност не „връщат“ нищо сами по себе си. Той преобразува входна стойност в нова стойност. Това не е същото като извеждането или връщането му от функцията. Самото приложение на функциятаестойността. Например, ако Add(N1, N2) -> N1+N2., Add(1, 2) е 3. Няма начин да върне нещо различно от 3, следователно можем да кажем, че е 3. Ето защо можете лесно да направите add_one = add(1) и след това add_one(2) е 3, add_one(5) е 6 и така На.

За тези, които се интересуват, вижте референтна прозрачност. За да направите тази точка по-ясна и да рискувате излишък, ето нещо, върху което да помислите:

когато f(x) е функция с една арност и преобразуването е f(x) -> x, тогава е убедително, че f(1) -> 1, f(2) -> 2, f(3.1416) -> 3.1416 и f("foo") -> "foo".

Това може да изглежда като безсмислено, но в нечиста функция няма такова гарантирано картографиране:

a = 1
def add_to_a(b):
return b + a

Сега a може да е всичко, преди add_to_a да бъде извикано. Така в Python можете да напишете чиста версия на горното като:

def add(a, b):
return a + b
or lambda a, b: a + b .

Сега е време да се впуснете в неизвестното.

Продължавайки напред с Erlang

merge([], [], Acc) -> Acc;

Първата клауза на функцията merge/3 означава, че когато първите два аргумента са празни списъци, картографирайте целия израз към (или „върнете“) третия аргумент Acc.

Интересното е, че в една чиста функция няма начин за запазване и мутиране на състояние извън себе си. Можем да работим само с това, което сме получили като входни данни във функцията, да го трансформираме, след което да подадем новото състояние в аргумента на друга функция (най-често това е друго рекурсивно извикване на себе си).

Тук Acc означава акумулатор, който можете да разглеждате като контейнер за състояние. В случая на merge/3, Acc е списък, който започва празен. Но докато рекурсивните извиквания се извършват, той натрупва стойности от първите два списъка, използвайки логиката, която програмираме (за която ще говорим по-нататък).

Този процес на изчерпване на стойност за изграждане на друга стойност е известен като редукция. Следователно в този случай можем да заключим, че тъй като първите два списъка са изчерпани (празни), Acc трябва да е узрял за вземане.

merge([], [H | T], Acc) -> [H | merge([], T, Acc)];

Втората клауза съответства на случая, когато първият списък вече е празен, но все още има поне още един елемент във втория списък. [H | T] означава, че списъкът има главен елемент H, който преминава към друг списък T. В Erlang списъкът е свързан списък и главата има указател към останалата част от списъка. Така че списък от [1, 2, 3, 4] може да се разглежда като:

%% match A, B, C, and D to 1, 2, 3, and 4, respectively
[A | [B | [C | [D | []]]]] = [1, 2, 3, 4].

В този случай, както можете да видите в примера за conning, T може да бъде просто празен опашен списък. Така че в този втори случай ние го съпоставяме със стойност на нов списък, в който елементът H от втория списък е свързан с рекурсивния резултат от извикването на merge/3, когато T е вторият аргумент.

merge([H | T], [], Acc) -> [H | merge(T, [], Acc)];

Третият случай е само обратната страна на втория случай. Съвпада със случая, когато първият списък не е празен, но вторият е. Тази клауза преобразува стойност в подобен модел, с изключение на това, че извиква merge/3 с опашката на първия списък като първи аргумент и запазва втория списък празен.

merge([Ha | Ta], [Hb | Tb], Acc) ->
  case Ha =< Hb of
    true  -> [Ha | merge(Ta, [Hb | Tb], Acc)];
    false -> [Hb | merge([Ha | Ta], Tb, Acc)]
  end.

Нека първо започнем с месото на merge/3. Тази клауза съответства на случая, когато първият и вторият аргумент са непразни списъци. В този случай въвеждаме case … of клауза (еквивалентна на превключване на главни букви на други езици), за да проверим дали заглавният елемент на първия списък (Ha) е по-малък или равен на заглавния елемент от втория списък (Hb).

Ако това е вярно, ние прехвърляме Ha върху резултантния списък на следващото рекурсивно извикване, за да се слеем с крайния списък на предишния първи списък (Ta) като нов първи аргумент. Запазваме втория и третия аргумент същите.

Тези клаузи представляват една единствена функция, merge/3. Можете да си представите, че може да е била клауза с една функция. Можем да използваме сложен случай ... от и/или ако е условен плюс съпоставяне на шаблони, за да отсеем всеки случай и да го съпоставим с правилния резултат. Това би го направило по-хаотично, когато можете лесно да прочетете всеки случай, функцията съвпада доста добре на отделни редове.

Нещата обаче станаха малко сложни за операцията за подразделяне, която се нуждае от две функции: half/1 и half/3.

half([]) -> {[], []};
half([X]) -> {[X], []};
half([X,Y]) -> {[X], [Y]};
half(L) ->
  Len = length(L),
  half(L, {0, Len}, {[], []}).
half([], _, {Acc1, Acc2}) ->
  {lists:reverse(Acc1), lists:reverse(Acc2)};
half([X], _, {Acc1, Acc2}) ->
  {lists:reverse(Acc1), lists:reverse([X | Acc2])};
half([H|T], {Cnt, Len}, {Acc1, Acc2}) ->
  case Cnt >= (Len div 2) of
      true -> half(T, {Cnt + 1, Len}, {Acc1, [H|Acc2]});
      false -> half(T, {Cnt + 1, Len}, {[H|Acc1], Acc2})
  end.

Това е мястото, където ще пропуснете Python и неговата разрушителна природа. На чисто функционален език списъците са свързани списъци. Когато работите с тях, няма връщане назад. Няма логика, която да казва „Искам да разделя списък наполовина, така че ще взема средния индекс и ще го разделя на две лява и дясна част. ”

Ако мислите ви са настроени да работят със свързани списъци, вие сте по-скоро в духа на „Мога да вървя само напред през списъка, като работя с няколко елемента наведнъж. Трябва да създам два празни списъка и да отчитам колко елемента съм извлякъл от изходния списък и съм ги поставил в първия, за да знам кога е време да превключа към друга кофа. Всичко гореспоменато трябва да бъде предадено като аргументи в рекурсивните извиквания.“ Уау!

С други думи, разрязването на списък наполовина може да се сравни с нарязването на блокче сирене с нож в средата му. От друга страна, функционалното сравнение за това е като да налеете кафе в две чаши еднакво – просто трябва да знаете кога е време да спрете да наливате в първата и да преминете към втората.

Функцията half/1, въпреки че не е наистина необходима, е там за удобство.

half([]) -> {[], []};
half([X]) -> {[X], []};
half([X,Y]) -> {[X], [Y]};
half(L) ->
  Len = length(L),
  half(L, {0, Len}, {[], []}).

Досега трябва да разберете какво прави всяка функционална клауза на Erlang. Новите двойки скоби тук представляват кортежи в Erlang. Да, връщаме лява и дясна двойка стойности, както във версията на Python. Функцията half/1 е тук, за да обработва прости, изрични основни случаи, които не гарантират стойността на предаването на други аргументи.

Обърнете внимание обаче на последния случай, когато аргументът има списък с повече от два елемента. (Забележка: тези с по-малко или равно на два елемента вече се обработват от първите три клаузи.) Той просто изчислява следното:

  • дължината на списъка L и извиква half/3 с L като първи аргумент
  • двойка променливи брояч и дължина на списъка, които ще се използват за сигнализиране на превключването от списък едно към списък две
  • и разбира се, чифт празни списъци за попълване на елементите от L in.
half([], _, {Acc1, Acc2}) ->
  {lists:reverse(Acc1), lists:reverse(Acc2)};

half/3 изглежда като бъркотия, но само за необучени очи. Първата клауза съответства на шаблон, когато списъкът с източници е източен. В този случай вторият чифт брояч и дължина няма да имат значение, тъй като вече е краят. Ние просто знаем, че Acc1 и Acc2 са узрели за отстъпване. Но чакайте, какво е с обръщането на двете?

Добавянето на елемент към свързан списък е много бавна операция. Изпълнява се O(N) пъти за всяко добавяне, защото трябва да създаде нов списък, да копира съществуващия върху него и да създаде указател към новия елемент и да го присвои на последния елемент. Това е като да преработите целия списък. Съчетайте това с рекурсии и сте обречени на катастрофа.

Единственият добър начин да добавите нещо към свързан списък е да го поставите в началото. Тогава всичко, което трябва да направи, е да създаде памет за тази нова стойност и да й даде препратка към главата на свързания списък. Проста O(1) операция. Така че, въпреки че можем да свържем списъци, използвайки ++ като [1, 2, 3] ++ [4], рядко искаме да го правим по този начин, особено с рекурсии.

Техниката тук е първо да обърнете списъка с източници, след това да поставите елемент върху него като [4 | [3, 2, 1]] и да ги обърнете отново, за да получите правилния резултат. Това може да звучи ужасно, но обръщането на списък и обръщането му обратно е O(2N) операция, която е O(N). Но между тях, подвеждането на елементи в списъка отнема само O(1), така че по същество не струва допълнително време за изпълнение.

half([H|T], {Cnt, Len}, {Acc1, Acc2}) ->
  case Cnt >= (Len div 2) of
      true -> half(T, {Cnt + 1, Len}, {Acc1, [H|Acc2]});
      false -> half(T, {Cnt + 1, Len}, {[H|Acc1], Acc2})
  end.

Връщане към half/3. Втората клауза, същността на функцията, прави точно същото като метафората за наливане на кафе, която посетихме по-рано. Тъй като списъкът с източници все още „излъчва“ данни, искаме да следим времето, през което сме изливали стойности от него в първата чаша кафе Acc1.

Помните ли, че в последната клауза на half/1 изчислихме дължината на оригиналния списък? Това е променливата Len тук и тя остава същата през всички извиквания. Той е там, за да можем да сравним Cnt брояча с него, разделен на 2, за да видим дали сме стигнали до средата на списъка с източници и трябва да преминем към попълване на Acc2. Това е мястото, където case … of идва.

Сега нека ги съберем всички заедно в mergesort/1. Това трябва да е толкова просто, колкото версията на Python и може лесно да се сравнява.

mergesort([A]) -> [A];
mergesort([A, B]) ->
  case A =< B of
      true -> [A,B];
      false -> [B,A]
  end;
mergesort(L) ->
  {Left, Right} = half(L),
  merge(mergesort(Left), mergesort(Right), []).

Това е!

В този момент или смятате, че това е нов и полезен начин за мислене върху проблем, или го намирате за просто объркващ. Но се надявам, че сте извлекли нещо от този програмен подход, което помага да хвърлите нова светлина върху начина, по който можем да мислим за алгоритмите.

Актуализация

Реализацията на Python на функцията merge не е ефективна, защото във всеки цикъл while първият елемент в списъка се премахва. Въпреки че това е често срещан модел във функционални езици като Erlang, в Python е много скъпо да се премахне или вмъкне елемент навсякъде, различно от последната позиция, защото за разлика от списък в Erlang, който е свързан списък, който е много ефективен за премахване или добавяне на елемент в началото на списъка списъкът на Python се държи като масив, който трябва да препозиционира всички останали елементи, когато някой бъде премахнат или добавен, което води до O(n) време на изпълнение.

По-добрият начин е да пожертвате малко място, за да дефинирате променлива на брояча за всеки списък, която може да бъде увеличена и използвана за достъп до текущия елемент от изходния списък, без изобщо да е необходимо да премахвате най-горния елемент.

def merge(a, b):
    out = []
    ai = 0
    bi = 0
    while (ai <= len(a) - 1 and bi <= len(b) - 1): 
        if (a[ai] <= b[bi]):
            out.append(a[ai])
            ai += 1
        else:
            out.append(b[bi])            
            bi += 1
    while (ai <= len(a) - 1):
        out.append(a[ai])
        ai += 1
    while (bi <= len(b) - 1):
        out.append(b[bi])
        bi += 1
    return out