Princíp triediaceho algoritmu merge sort (alebo ak chcete po slovensky, triedenia spájaním) je jednoduchý. Použijeme metódu, známu pod názvom rozdeľ a panuj. Tá spočíva v tom, že ak veľký problém nevieme vyriešiť, rozdelíme ho na menšie, ktoré už možno riešiť vieme.
Začnime ale tým, že vyriešime jednoduchší problém. Majme dve utriedené polia čísel. Ako vyrobiť jedno utriedené pole, tvorené všetkými týmito číslami?
Stačí si všimnúť, že najmenšie zo všetkých čísel je na začiatku jedného z polí. Toto číslo presunieme do výsledného poľa... a môžeme celú úvahu zopakovať. Vždy pozrieme na čísla na začiatku každého z polí, vyberieme menšie z nich a to dáme na koniec výsledného poľa.
Čo sa týka konkrétnej implementácie, nechceme prvky z polí vyhadzovať,
lebo to zaberá príliš veľa času. Radšej si zoberieme dve premenné,
ktoré budú ukazovať na pomyselné začiatky polí.
Ak teda vyhodíme prvok zo začiatku poľa, znamená to,
že len o 1 zväčšíme premennú ukazujúcu na jeho začiatok.
Tiež si treba dať pozor, a kontrolovať, či sme niektoré pole nevyčerpali celé,
aby sme nevypadli mimo pamäť.
No a späť k triedeniu. Jedno číslo sa triedi ľahko, ba aj s dvomi si vieme poradiť :) Nuž, ale čo ak ich máme viac? Vtedy rozdelíme pole, ktoré máme utriediť, na dve zhruba rovnako veľké časti. Každú z nich utriedime samostatne. Jediné, čo ešte potrebujeme, je spojiť dve utriedené polia do jedného. A ajhľa, tento problém sme pred chvíľkou vyriešili.
Hm, moment. Čo vlastne znamená "každú z nich utriedime samostatne"? Ako ich utriedime? Jednoducho: buď už sú tie časti dosť krátke na to, aby sme ich utriedili rovno, alebo použijeme opäť presne ten istý postup – rozdeliť na dve časti, atď.
No a slová "použijeme presne ten istý postup" napovedajú, že najľahším spôsobom, ako implementovať merge sort, bude rekurzia (ak nepoznáte rekurziu, zoznámiť sa s ňou môžete v samostatnom článku o rekurzii). Myšlienka teda bude nasledovná:
def mergesort(A):
# ak je pole dost male, uz je rovno utriedene
if len(A)==1:
return A
# rozdel pole A na dve rovnako velke polia B a C...
B, C = ...
# ...utried polia samostatne...
B = mergesort(B)
C = mergesort(C)
# ...a vysledok uloz do A
return merge(B,C)