Geek tričko zdarma Python týden
Tričko zdarma! Stačí před dobitím bodů použít kód TRIKO15. Více informací zde
Pouze tento sleva až 80% na kurzy Python

Merge Sort

Unicorn College Tento obsah je dostupný zdarma v rámci projektu IT lidem.
Vydávání, hosting a aktualizace umožňují jeho sponzoři.

Merge sort je algoritmus, založený na tzv. principu rozděl a panuj (latinsky divide et impera, anglicky divide and conquer). To znamená, že pokud nějaký problém neumíme vyřešit v celku, rozložíme si ho na více menších a jednodušších problémů. Ten samý postup aplikujeme i na tyto problémy (opět je rozdělíme na ještě menší, mimochodem velmi se zde nabízí rekurzivní řešení) až se dostaneme na takovou úroveň, kterou jsme schopni bez problému řešit. V problému třídění se často chceme dostat až k poli velikosti 1, které považujeme automaticky za setříděné.

Merge sort operuje s myšlenkou, že dokážeme velmi rychle a v lineárním čase slít (spojit, anglicky merge) dvě již setříděná pole do jednoho tak, aby výsledné pole bylo opět setříděné. Na začátku samozřejmě máme jen jedno pole a to setříděné není. My si ho však můžeme rekurzivně rozdělit na 2 poloviny, každou polovinu opět rozdělit na další poloviny a tak dále. V nejhlubší hladině rekurze se nutně dostaneme do fáze, kdy nám zbydou už jen samá jednoprvková pole. Jednoprvkové pole můžeme považovat za setříděné, říká se o něm, že je setříděné triviálně. Jak se postupně vynořujeme z rekurze, sléváme tato jednoprvková pole na dvouprvková, ta na čtyřprvková a tak pokračujeme, dokud nám nezbydou dvě velká pole, která když slijeme, dostaneme naše původní pole setříděné. Protože sléváme vždy po rozdělení na poloviny, budeme to jistě dělat log n krát (kde základem logaritmu je 2, protože dělíme na 2 poloviny). Samotné slévání zvládneme v čase O(n), výsledná časová složitost algoritmu tedy bude O(n log n). Nejprve si ukážeme, jak se pole slévají.

Slévání

Mějme 2 pole, která jsou již setříděná:

2 3 5
1 4 7 8

Všimněte si, že pole nemusí mít stejnou velikost. Když budeme v Merge sortu dělit na polovinu pole o velikosti 7, dostaneme přesně takováto pole. Úskalím Merge sortu je fakt, že budeme potřebovat pomocnou paměť, ta bude zatím prázdná.

2 3 5
1 4 7 8

Pomocná paměť:

             

Začneme tedy slévat. V každém poli budeme potřebovat 2 indexy, které budou zpočátku na prvním indexu. Zde budou zobrazeny tučně.

2 3 5
1 4 7 8

Pomocná paměť:

             

Porovnáme prvky na indexech a ten menší prvek vložíme do pomocného pole na pozici, která je součtem indexů. Oba indexy máme nyní na pozici 0 (první pozice), pozice v pomocném poli tedy bude 0 + 0 = 0. Porovnáme a zjistíme, že 1 < 2, vložíme tedy jedničku na pozici 0 do pomocného pole a index u jedničky zvětšíme o 1.

2 3 5
1 4 7 8

Pomocná paměť:

1            

2 < 4, vložíme tedy dvojku na 0 + 1 = 1 a posuneme se s indexem.

2 3 5
1 4 7 8

Pomocná paměť:

1 2          

3 < 4, vložíme 3 na pozici 1 + 1 = 2, posuneme se s indexem.

2 3 5
1 4 7 8

Pomocná paměť:

1 2 3        

Pokračujeme dále...

2 3 5
1 4 7 8

Pomocná paměť:

1 2 3 4      

 

2 3 5
1 4 7 8

Pomocná paměť:

1 2 3 4 5    

Nyní jsme se dostali do fáze, kdy jsme alespoň s jedním indexů již vyjeli z pole. Nyní se podíváme, zda druhý index není ještě v poli (zde je) a dolijeme zbylé prvky.

2 3 5
1 4 7 8

Pomocná paměť:

1 2 3 4 5 7 8

Máme hotovo, výsledné pole je setříděné. V praxi samozřejmě nedostaneme pole už takto připravené na 2 setříděné poloviny, ale pořádně rozházené. Musíme se tedy rekurzí dostat až na jednotková pole a ty poté začít slévat.

Průběh

Průběh označuje následující diagram:

Merge sort

Možná vylepšení

Kamenem úrazu algoritmu je potřebná pomocná paměť. Když se podíváte na diagram výše, vidíte, co všechno si musí funkce držet v paměti. Mohli bychom ovšem třídit naopak, tedy brát původní pole jako již rozdělené na pole jednotková a ta rovnou slévat na pole velikosti 2, ty pak na pole velikosti 4 a podobně. Pomocné paměti bychom se nezbavili, ale při troše práce by stačilo jen jedno pomocné pole, které by bylo stejně velké, jako pole původní. Do něj bychom si uložili výsledek po slití a potom slévali do pole původního a zas naopak. Přelévali bychom tedy data střídavě mezi těmito poli.

Video ukázka

Vlastnosti algoritmu

Časová složitost O(n log n)
Stabilita Ano
Rychlost Rychlý

Pozn. je myšlena časová složitost průměrného případu a rychlost vzhledem ke všem třídícím algoritmům

Zdrojový kód

// sliti dvou setridenych poli do jednoho
public static void merge(int[] list, int[] left, int[] right) {
  int i = 0;
  int j = 0;
  // dokud nevyjedeme z jednoho z poli
  while ((i < left.length) && (j < right.length)) {
    // dosazeni toho mensiho prvku z obou poli a posunuti indexu
    if (left[i] < right[j]) {
      list[i + j] = left[i];
      i++;
    }
    else {
      list[i + j] = right[j];
      j++;
    }
  }
  // doliti zbytku z nevyprazdneneho pole
  if (i < left.length) {
    while (i < left.length) {
      list[i + j] = left[i];
      i++;
    }
  }
  else {
    while (j < right.length) {
      list[i + j] = right[j];
      j++;
    }
  }
}

// samotne trideni
public static void merge_sort(int[] list) {
  if (list.length <= 1) //podmínka rekurze
  return ;
  int center = list.length / 2; //stred pole
  int[] left = new int[center]; //vytvoreni a naplneni leveho pole
  for (int i = 0; i < center; i++)
  left[i] = list[i];
  int[] right = new int[list.length - center]; //vytvoreni a naplneni praveho pole
  for (int i = center; i < list.length; i++)  //vytvoreni a naplneni praveho pole
  right[i - center] = list[i];
  merge_sort(left); // rekurzivni zavolani na obe nova pole
  merge_sort(right);
  merge(list, left, right); //sliti poli
}
// sliti dvou setridenych poli do jednoho
public static void merge(int[] list, int[] left, int[] right) {
  int i = 0;
  int j = 0;
  // dokud nevyjedeme z jednoho z poli
  while ((i < left.Length) && (j < right.Length)) {
    // dosazeni toho mensiho prvku z obou poli a posunuti indexu
    if (left[i] < right[j]) {
      list[i + j] = left[i];
      i++;
    }
    else {
      list[i + j] = right[j];
      j++;
    }
  }
  // doliti zbytku z nevyprazdneneho pole
  if (i < left.Length) {
    while (i < left.Length) {
      list[i + j] = left[i];
      i++;
    }
  }
  else {
    while (j < right.Length) {
      list[i + j] = right[j];
      j++;
    }
  }
}

// samotne trideni
public static void merge_sort(int[] list) {
  if (list.Length <= 1) //podmínka rekurze
  return ;
  int center = list.Length / 2; //stred pole
  int[] left = new int[center]; //vytvoreni a naplneni leveho pole
  for (int i = 0; i < center; i++)
  left[i] = list[i];
  int[] right = new int[list.Length - center]; //vytvoreni a naplneni praveho pole
  for (int i = center; i < list.Length; i++) //vytvoreni a naplneni praveho pole
  right[i - center] = list[i];
  merge_sort(left); // rekurzivni zavolani na obe nova pole
  merge_sort(right);
  merge(list, left, right); //sliti poli
}
// sliti dvou setridenych poli do jednoho
procedure merge(var list, left, right: array of integer);
var i, j: integer;
begin
  i:=0;
  j:=0;
  // dokud nevyjedeme z jednoho z poli
  while ((i < length(left)) and (j < length(right))) do begin
    // dosazeni toho mensiho prvku z obou poli a posunuti indexu
    if (left[i] < right[j]) then begin
      list[i + j]:=left[i];
      inc(i);
    end else begin
      list[i + j]:=right[j];
      inc(j);
    end;
  end;
  // doliti zbytku z nevyprazdneneho pole
  if (i < length(left)) then begin
    while (i < length(left)) do begin
      list[i + j]:=left[i];
      inc(i);
    end;
  end else begin
    while (j < length(right)) do begin
      list[i + j]:=right[j];
      inc(j);
    end;
  end;
end;

// samotne trideni
procedure merge_sort(var list: array of integer);
var center, i: integer;
    left, right: array of integer;
begin
  if (length(list) <= 1) then exit; // podminka rekurze
  center:=length(list) div 2; // stred pole
  setlength(left, center); // vytvoreni a naplneni leveho pole
  for i:=0 to (center - 1) do
  left[i]:=list[i];
  setlength(right, length(list) - center); // vytvoreni a naplneni praveho pole
  for i:=center to (length(list) - 1) do
  right[i - center]:=list[i];
  merge_sort(left); // rekurzivni zavolani na obe nova pole
  merge_sort(right);
  merge(list, left, right); // sliti poli
end;
# sliti dvou setridenych poli do jednoho
def merge(list, left, right)
  i = 0
  j = 0
  # dokud nevyjedeme z jednoho z poli
  while ((i < left.length) && (j < right.length))
    # dosazeni toho mensiho prvku z obou poli a posunuti indexu
    if (left[i] < right[j])
      list[i + j] = left[i]
      i += 1
    else
      list[i + j] = right[j]
      j += 1
    end
  end
  # doliti zbytku z nevyprazdneneho pole
  if (i < left.length)
    while (i < left.length)
      list[i + j] = left[i]
      i += 1
    end
  else
    while (j < right.length)
      list[i + j] = right[j]
      j += 1
    end
  end
end

# samotne trideni
def merge_sort(list)
  return if (list.length <= 1) # podminka rekurze
  center = list.length / 2 # stred pole
  left = Array.new(center) # vytvoreni a naplneni leveho pole
  center.times { |i| left[i] = list[i] }
  right = Array.new(list.length - center) # vytvoreni a naplneni praveho pole
  center.upto(list.length - 1) { |i| right[i - center] = list[i] }
  merge_sort(left) # rekurzivni zavolani na obe nova pole
  merge_sort(right)
  merge(list, left, right) # sliti poli
end

 

 

Článek pro vás napsal David Čápka
Avatar
Jak se ti líbí článek?
4 hlasů
Autor pracuje jako softwarový architekt a pedagog na projektu ITnetwork.cz (a jeho zahraničních verzích). Velmi si váží svobody podnikání v naší zemi a věří, že když se člověk neštítí práce, tak dokáže úplně cokoli.
Unicorn College Autor sítě se informační technologie naučil na Unicorn College - prestižní soukromé vysoké škole IT a ekonomie.
Předchozí článek
Heapsort
Všechny články v sekci
Třídící/řadící algoritmy
Miniatura
Následující článek
Quick sort
Aktivity (2)

 

 

Komentáře
Zobrazit starší komentáře (5)

Avatar
David Čápka
Tým ITnetwork
Avatar
David Čápka:25.11.2013 20:03

Díky, kouknu na to :)

Odpovědět 25.11.2013 20:03
Jsem moc rád, že jsi na síti, a přeji ti top IT kariéru, ať jako zaměstnanec nebo podnikatel. Máš na to! :)
Avatar
xxx
Člen
Avatar
xxx:26.4.2014 17:12

nie je v tom obrazku chyba (Prubeh)? lebo pole je 5295318 a potom ked sa deli tak je ze 592 a nie 529, druha cast je ok 5318
inak skvele tutorialy k algoritmom, tie videa sa mi moc pacia :)

Odpovědět  +1 26.4.2014 17:12
kto chce hlada sposoby, kto nechce hlada dovody...
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:30.6.2017 13:01
  1. U slevani bych zkopirovane prvky do druheho pole bud vymazal a nebo dal svetle sedou barvou.
  2. Algoritmu, kdy za serazena pole povazujene jednotlive prvky a pak to jen slevame, bych nezatracoval a mam i kod

http://mlich.zam.slu.cz/…sorting3.htm - 1 sortListMerge_2a

  • pouziva ho Firefox
  • je to stejne rychle jako quicksort
  • pocet porovnani (cmp funkce v kodu) je mensi nez quick-sort
  • u vice vlaknovych procesoru lze docilit 3x vetsi rychlosti nez u linearniho serazeni, protoze uz od zacatku muzete porovnavat 50% prvku naraz
  • algoritmus vraci ukazatel pameti, tudiz neni treba vsechny prvky presouvat do puvodniho pole
  • samozrejme, pro textove retezce je lepsi udelat pole s ukazateli pameti a presouvat ukazatele, az na zaver presunout prvky v poli
  • je mozne to napsat i pres jedno pole, ale cely algoritmus ti pak brzdi schopnosti pc, kdy musis pri presunu prvku u velkych poli cele pole rotovat. viz na me strance XsortListMerge5_1a

3. Urcite bych pridal jako detekci serazenych poli porovnani sousednich policek. Takto lze algoritmus pri serazeni asc / desc hned ukoncit a vrati zpet serazene pole.

4. Mozna by stalo za zminku, ze Tim Sort, v soucastnosti nej algoritmus, pouziva hybrid insert-sort (male pole) + slevani (velke pole)

 
Odpovědět 30.6.2017 13:01
Avatar
Lukáš Kún
Člen
Avatar
Lukáš Kún:6.11.2017 1:32

Moje C# verze bez rekurze:

static T[] MergeSort<T>(T[] pole)
            where T : IComparable<T>
        {
            if (pole.Length < 2)
                return pole;

            T[] buff = new T[pole.Length];
            bool poleDoBuff = true;
            int pp = 1;
            while (pole.Length / pp >= 1)
            {
                T[] poleZ = poleDoBuff ? pole : buff;
                T[] poleDo = poleDoBuff ? buff : pole;

                int bi = 0;
                while (bi < poleDo.Length)
                {
                    int li = bi;
                    int lk = ((li + pp) > poleDo.Length) ? poleDo.Length : (li + pp);
                    int pi = lk;
                    int bk = ((pi + pp) > poleDo.Length) ? poleDo.Length : (pi + pp);

                    while (bi < bk)
                    {
                        if (li == lk)
                            poleDo[bi++] = poleZ[pi++];
                        else if (pi == bk)
                            poleDo[bi++] = poleZ[li++];
                        else
                        {
                            switch (poleZ[li].CompareTo(poleZ[pi]))
                            {
                                case 1:
                                    poleDo[bi++] = poleZ[pi++];
                                    break;
                                case -1:
                                    poleDo[bi++] = poleZ[li++];
                                    break;
                                case 0:
                                    poleDo[bi++] = poleZ[li++];
                                    poleDo[bi++] = poleZ[pi++];
                                    break;
                            }
                        }
                    }
                }
                poleDoBuff = !poleDoBuff;
                pp *= 2;
            }

            return poleDoBuff ? pole : buff;
        }

Testováno celkem dlouho testem generujícím náhodně dlouhá pole s náhodnými čísly - vše prošlo, tak snad by to mělo fungovat. Ovšem nejsem žádný profík, takže kdo ví :D

Případné námitky rád uvítám.

 
Odpovědět 6.11.2017 1:32
Avatar
Patrik Pastor:19. dubna 21:38

chtel bych se zeptat, zda podminka if (list.length <= 1) //pokud je kazde pole jednoprvkove

by nemohlo by ve while-podmince:

(while list.length <= 1){
..
..
}
merge(list, left, right);

Tedy, neni mi jasne na konci, zda k metode "merge" vubec dojde (kdyz se v rekurzivnim volani deli pole az na 1-prvkova pole, a tu ranu je vyhodi podminka
if (list.length <= 1) return;

Takze kdy vlastne dochazi k tomu slevani, kdyz se to deli na 1-n pole, ale to znici metodu, kdy tedy dojde ke konecnemu slevani? predem diky

 
Odpovědět 19. dubna 21:38
Avatar
Odpovídá na Peter Mlich
Patrik Pastor:21. dubna 8:46

jak je to s tou rekurzi a slitim. Kdzy je podminka rekurze, ze se mi vrati z metody pri velikosti pole 1 (a mensi, ale mensi uz nebude, kdyz to dojde nejdriv na 1ku), tak ani k tomu sliti prece nedojde, protoze rekurze je volana PRED slitim. Nebo se vola rekurze, interpet pokracuje na prikaz sliti(merge)?

 
Odpovědět 21. dubna 8:46
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Patrik Pastor
David Čápka:21. dubna 11:58

To je správně, že je rekurze volaná před slitím, až se zní vystoupí a program se tam vrátí, tak se oba výsledky rekurze slijí a vznikne tak nový výsledek rekurze, který se vrátí a tak dále. Z toho co jsi napsal mi přijde, že ti není úplně jasné jak rekurze funguje. Dej si na konec metody break point a odkrokuj si algoritmus v IDE.

Máš to na tom obrázku. Na konci metody se volá vždy slití. To se neprovede jen v případě, že je pole o velikosti 1. Takže se to vše rekurzivně provolá až zbude pole o velikosti 1. Teď se rekurze ukončí a výsledek se postupně začne vracet do řetězce metod, jak čekají na výsledek. Metodě, která měla pole o velikosti větší než 1, se pak vrátí 2 pole o jednom prvku a ona je slije. Metodě, co ji volala, se opět vrátí tento výsledek a ten slije s výsledkem druhé metody, kterou spolu s ní zavolala a tak dále.

Odpovědět  +1 21. dubna 11:58
Jsem moc rád, že jsi na síti, a přeji ti top IT kariéru, ať jako zaměstnanec nebo podnikatel. Máš na to! :)
Avatar
Odpovídá na David Čápka
Patrik Pastor:21. dubna 12:36

aha. Ja jsem totiz myslel, ze jak je ta rekurzivni podminka (if pole.length <= 1) return. Tak ze to slovicko "return" v te podmince celou metodu znici (ve smyslu ze program uz je MIMO tuto metodu (diky tomu return), a ke sliti by tedy nedoslo, protoze to sliti je UVNITR metody, ale prace tim return by uz program byl mimo metodu. Doufam ze rozumis, jak to myslim, ale ted chapu.

 
Odpovědět 21. dubna 12:36
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Patrik Pastor
David Čápka:21. dubna 12:56

No to tak také je, nic po return se už nezavolá. Ale ta metoda, i když se násilně ukončí pomocí return, byla zavolána před slitim z předchozí metody. Program se tam tedy vrati a výsledky slije. Kdyz zavoláš někde nějakou metodu, program si to pamatuje a po jejím ukončení jakýmkoli způsobem se na toto místo vrátí. Psal jsem ti, ať si to odkrokujes, pak to uvidíš hned :-) Vážně si to zkus.

Editováno 21. dubna 12:57
Odpovědět 21. dubna 12:56
Jsem moc rád, že jsi na síti, a přeji ti top IT kariéru, ať jako zaměstnanec nebo podnikatel. Máš na to! :)
Avatar
 
Odpovědět 21. dubna 13:04
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 10 zpráv z 15. Zobrazit vše