Josef Troch (troch@mail.ru)
14.4.2002

Úloha:

R₁ ... R_k

R_k+1 ... R_n

Nevyhovující řešení:

Jednodušší algoritmus (M. A. Kronrod):

Algoritmus:

1. Buď s=n . Rozdělíme pole (obsahující zmíněné posloupnosti) na bloky délky s, poslední blok (necelý) bude mít délku n mod s (což může být 0). Označme počet celých bloků m + 1, bloky označme B₁ ... B_m, B_m+1, B_m+2 (kde B_m+2 je ten necelý popř. prázdný blok).
   
2. Nyní vyměníme prvky v bloku B_m+1 s blokem obsahujícím prvek R_k. Pole tedy nyní má tuto strukturu:
   B₁ ... B_m , A
   - kde každý z bloků B₁ ... B_m má právě s prvků, setříděných do neklesající posloupnosti a A je pomocná (auxiliary) oblast obsahující t prvků, pro nějaké t, kde s t < 2s . (A obsahuje právě prvky z bloku, který obsahoval R_k a z bloku B_m+2 .}
3. Najdeme blok s nejmenším prvním (=nejlevějším) prvkem (porovnáváme tedy prvky v poli na pozicích 1, s + 1, ..... (m - 1).s + 1) a vyměníme tento blok s blokem B₁ . Pak najdeme blok s druhým nejmenším nejlevějším prvkem a vyměníme ho s B₂ atd. Bloky jsou tedy nyní uspořádány tak, že jejich nejlevější prvky tvoří neklesající posloupnost. Zároveň platí, že počet inverzí (viz níže) libovolného prvku v oblasti B₁ ... B_m je menší než s (viz níže).
4. Nyní slijeme blok B₁ s blokem B₂ následujícím způsobem: Vyměníme B₁ s prvními s prvky v A (označme tuto oblast A'). Pak sléváme blok B₂ s prvky z oblasti A' (tedy s bývalým obsahem bloku B₁) do oblasti B₁B₂ tak, že vyměňujeme prvky B₁B₂ s těmi, které přichází na jejich místo coby slitá posloupnost (viz př. č. 2). Tímto zrušíme uspořádání prvků v oblasti A'.
   Stejným způsobem poté slijeme B₂ s B₃, pak B₃ s B₄, .... B_m-1 s B_m. Nyní máme setříděnu celou oblast B₁ ... B_m (viz níže).
5. Setřídíme oblast prvků R_n-2t+1 ... R_n (tedy 2t posledních prvků v poli - bez ohledu na hranice bloků) pomocí třídění přímým výběrem (straight selection sort - viz [Knuth]). (Obecně lze použít libovolnou metodu pracující na místě v čase O((2t)²)=0(n) .) Tímto dostaneme t největších prvků do oblasti A.
6. Slijeme oblasti R_n-2t+1 ... R_n-t a R₁ ... R_n-2t s použitím pomocné oblasti A (obdobně jako dříve). Nyní máme opět setříděnu celou oblast B₁ ... B_m, avšak oblast A již obsahuje t největších prvků.
7. Setřídíme oblast A přímým výběrem. Nyní máme setříděné již celé pole.

Příklad

Proč algoritmus funguje:

• Definujme počet inverzí prvku R_i jako počet prvků R_j takových, že R_j > R_i a zároveň j < i. (Tedy počet prvků, které jsou větší než R_i, ale jsou před ním v poli.)
• Tvrzení 1.1: Po 3. kroku algoritmu platí, že počet inverzí libovolného prvku (označme ho R_i) z oblasti B₁ ... B_m je menší než s.
  
  Důkaz: Označme blok obsahující R_i jako B_x. Uvažujme blok B_y nacházející se v oblasti před R_i.
  1. Tento blok může pocházet ze stejné vstupní posloupnosti jako R_i , v tomto případě ale B_x a B_y jsou 2 celistvé úseky jedné ze vstupních posloupností a nejlevější prvek B_y je nejlevější prvek bloku B_x , a proto všechny prvky v B_y jsou než R_i. Tento blok nám tedy nezvýší počet inverzí.
  2. Pokud ovšem B_y náležel do druhé vstupní posloupnosti než R_i , můžeme rozlišit 2 případy. Buď je nejpravější prvek (a tedy i všechny ostatní prvky) B_y R_i - počet inverzí se nám nezvýší; nebo je nejpravější prvek B_y větší než R_i - ovšem nejlevější prvek B_y je určitě nejlevější prvek bloku B_x a tudíž B_y nám zvýší počet inverzí maximálně o s - 1 . Nicméně takovýto blok se může před R_i vyskytnout pouze jeden - pokud by někde za B_y následoval druhý blok ze stejné posloupnosti, jeho nejlevější prvek by musel být větší nebo roven nejpravějšímu prvku B_y , ovšem tím by byl větší než R_i a tedy i větší než nejlevější prvek B_x, tedy by následoval v poli až za R_i.
• Tvrzení 1.2: Po 4. kroku algoritmu je setříděna již celá oblast B₁ ... B_m .
  
  Důkaz: Ukážeme, že počet inverzí libovolného prvku z dané oblasti je po 4. kroku algoritmu 0, a tedy je posloupnost setříděná (protože před žádným prvkem R_i není prvek větší než R_i).
  Pro libovolný prvek R_i z dané oblasti před tímto krokem platilo, že jeho počet inverzí je menší než s. Označme blok obsahující R_i jako B_x , předpokládejme, že x ≠ 1 (při x = 1 je počet inverzí R_i již před tímto krokem roven 0). V okamžiku, kdy sléváme blok B_x s blokem B_x-1, B_x-1 obsahuje s největších prvků ležících před R_i a tedy po slití těchto dvou bloků klesne počet inverzí prvku R_i na 0 (a blok B_x bude opět obsahovat s největších prvků z oblasti B₁ ... B_x).

Časová složitost:

1. V tomto kroku se jen vypočítají s a m, což lze v čase O(1).
2. Výměna dvou bloků zabere triviálně čas O(s).
3. Nalezení bloku s nejmenším nejlevějším prvkem zabere O(m), výměna dvou bloků O(s). Toto opakujeme m - 1 krát, tedy celkový čas je O(m .(m + s)).
4. Slití dvou bloků zabere čas O(s), tedy celý tento krok O(m . s).
5. Třídění přímým výběrem - O((2t)²).
6. Slití těchto 2 posloupností potřebuje čas O(n).
7. Třídění přímým výběrem - O(t²).

Poznámky k algoritmu:

• Algoritmus není stabilní (stable) - tedy nezachovává pořadí stejně velkých prvků. Toto lze postřehnout z př. č. 2, kde se v závislosti na obsazích slévaných bloků permutují prvky v pomocné oblasti A'.
• Algoritmus zjevně není příliš efektivní.
• [Knuth] všude používá místo třídění přímým výběrem insertsort, tedy třídění vkládáním.

Rychlejší algoritmus (B. C. Huang & M. A. Langston):

Zjednodušená varianta algoritmu:

1. Spočteme s a rozdělíme pole na bloky délky s. Bloky označme B₁ ... B_s . Nejlevější prvek bloku B_i označme head(B_i ), nejpravější tail(B_i ).
   Použijeme algoritmus z předpokladů, čímž přesuneme s největších prvků pole na jeho počátek.
2. Setřídíme bloky B₂ ... B_s podle jejich nejpravějších prvků (tail(B_i )) - obdobně jako v 3. kroku Kronrodova algoritmu).
3. Nyní vybereme 2 "běhy", které budeme slévat. Prvním běh budou bloky B₂ ... B_i (i  2), kde B_i je první blok takový, že tail(B_i ) > head(B_i+1 ). Druhý běh bude sestávat pouze z bloku B_i+1.
4. Pomocnou (auxiliary) oblastí (tu zde chápeme jako sadu prvků, ne sadu pozic jako v Kronrodově algoritmu!) je momentálně blok B₁. Sléváme první a druhý běh tak, že vždy porovnáme nejlevější nepřesunutý prvek v 1. běhu s nejlevějším nepřesunutým prvkem v 2. běhu a ten menší z nich (jsou-li stejné, bereme ten levý) vyměníme s nejlevějším prvkem pomocné oblasti. Pomocná oblast se nám tedy v průběhu slévání typicky rozdělí na 2 části (a její prvky se v poli postupně přesouvají doprava).
   Slévání ukončíme v okamžiku, kdy tail(B_i ) je přesunut na svou finální pozici. V tomto okamžiku je rovněž pomocná oblast jedním souvislým úsekem, ačkoliv nemusí začínat na hranici bloku. Z bloku B_i+1 nám musel zůstat 1 či více nepřesunutých prvků (protože bloky byly setříděny dle svých tail(...) - tedy tail(B_i )  tail(B_i+1 ) a v případě stejných prvků jsme vzali ten levý).
5. Vybereme nové 2 běhy - první běh bude začínat nejlevějším nepřesunutým prvkem z B_i+1 a končit (analogicky ke kroku 3.) prvkem tail(B_j ) (j  i+1), kde B_j je první blok (popř. ten nepřesunutý zbytek bloku B_i+1) takový, že tail(B_j ) > head(B_j+1 ). Druhý běh bude odpovídat bloku B_j+1. Tyto běhy výše uvedeným způsobem slijeme (s použitím té pomocné oblasti, která se nám posunula doprava). Pokračujeme tedy cyklicky v hledání běhů a jejich slévání, do okamžiku, kdy se nám podaří nalézt již jen jediný běh.
6. Tento běh tedy posuneme doleva ("rotace") tak, že se nám pomocná oblast dostane na pravý konec pole (jak toto provést efektivně viz níže).
7. Na závěr setřídíme pomocnou oblast přímým výběrem. Máme setříděno celé pole.

Příklad

Proč algoritmus funguje:

• Definujme počet opačných inverzí prvku R_i jako počet prvků R_j takových, že R_j < R_i a zároveň j > i. (Tedy zcela obráceně k definici inverze v Kronrodově algoritmu - počet prvků, které jsou menší než R_i, ale jsou za ním v poli.)
• Tvrzení 2.1: Po provedení 2. kroku je počet opačných inverzí libovolného prvku v oblasti B₂ ... B_s menší než s, všechny tyto inverze pocházejí ze stejného bloku.
  
  Důkaz: (Dokazované tvrzení je "převráceným" tvrzením k 1. tvrzení u Kronrodova algoritmu, důkaz je také principielně stejný, proto jen stručně.)
  Zvolme libovolný prvek R_i neležící v pomocné oblasti. Označme blok, který ho obsahuje B_x. Uvažujme blok B_y nacházející se v oblasti za R_i.
  1. Tento blok může pocházet ze stejné vstupní posloupnosti jako R_i , v tomto případě jsou všechny jeho prvky větší nebo rovny R_i, neboť bloky jsou setříděny dle nejpravějších prvků. Počet opačných inverzí se nám nezvýší.
  2. Pokud B_y náležel do druhé vstupní posloupnosti než R_i, můžeme rozlišit 2 případy. Buď je head(B_y ) (a tedy i všechny ostatní prvky B_y ) větší nebo roven R_i - počet opačných inverzí se nám nezvýší; nebo je head(B_y ) < R_i - ovšem tail(B_y )  tail(B_x )  R_i a tudíž B_y nám zvýší počet opačných inverzí maximálně o s - 1 . Ale takovýto blok se může za R_i vyskytnout pouze jeden - pokud by někde za B_y následoval druhý blok ze stejné posloupnosti, všechny jeho prvky by byly  tail(B_y )  R_i.
• Tvrzení 2.2: Po provedení 5. kroku algoritmu je část pole vlevo od pomocné oblasti setříděna, libovolný prvek vpravo od pomocné oblasti je libovolnému prvku vlevo od něj (s vyjímkou prvků z pomocné oblasti).
  
  Důkaz:Ukážeme, že počet opačných inverzí libovolného z prvků vpravo od pomocné oblasti je po 5. kroku algoritmu 0, a tedy je příslušná část posloupnosti setříděná (protože každému prvku předchází všechny prvky menší než on).
  Zvolme libovolný prvek R_i vpravo od pomocné oblasti.
  1. Předpokládejme, že se tento prvek vyskytnul při (některé iteraci) slévání běhů v prvním běhu. Tento první běh končil prvkem tail(B_j ) takovým, že tail(B_j ) > head(B_j+1 ), při čemž druhý běh sestával pouze z bloku B_j+1 . Protože tail(B_j ) > head(B_j+1 ) s využitím tvrzení 2.1 dostáváme, že všechny opačné inverze prvku tail(B_j ) pochází z bloku B_j+1  a tedy po slití těchto běhů se počet opačných inverzí prvku tail(B_j ) změní na 0, tudíž i počet opačných inverzí prvku R_i se změní na 0.
  2. Pokud se prvek z R_i vyskytnul v 2. běhu při některé iteraci slévání a byl slit (tedy nepřipadl do 1. běhu v další iteraci), pak R_i < než nejlevější prvek prvního běhu - ten má ale počet obrácených inverzí 0 (viz výše) a tudíž i R_i má počet obrázených inverzí 0.
  Druhá část tvrzení je zřejmá - protože prvky vpravo od pomocné oblasti tvoří jediný běh, jsou vzájemně vůči sobě uspořádané; jelikož všechny prvky vlevo od pomocné oblasti mají počet obrázených inverzí = 0, žádný z nich není větší než libovolný prvek vpravo od pomocné oblasti.
• Tedy po provedení kroku 6. je posloupnost v B₁ ... B_s-1 setříděna a blok B_s obsahuje s největších prvků celého pole. Ty setřídíme v kroku 7., čímž je úloha vyřešena.

Časová složitost:

Jak upravit vstup tak, aby splňoval předpoklady pro zjednodušenou variantu algoritmu:

• Nejdříve vyřešíme specielní případ, kdy délka jedné ze vstupních posloupností je k < n. Bez újmy na obecnosti předpokládejme, že tato "krátká" posloupnost je ta první, tedy R₁ ... R_k. V tomto případě lze slévání provést efektivně pomocí metody "block merge forward" popsané v [Pardo].
  Porovnáme R₁ a R_k+1 - je-li R₁  R_k+1 je R₁ na své finální pozici. Pokud R₁ > R_k+1, najdeme prvek R_p takový, že R_p < R₁  R_p+1 a pak všechny prvky R₁ ... R_p cyklicky posuneme ("rotace" - jak ji provést v čase O(p) viz níže) o p - 1 pozic doprava - tedy nejpravější prvek té "krátké" posloupnosti bude na p-té pozici v poli. Tento prvek a všechny prvky vpravo od něj jsou nyní na svých finálních pozicích. Pokračujeme ve slévání - iterujeme stejný postup pro oblast pole R_p+1 ... R_n. V okamžiku, kdy všechny prvky jedné z původních posloupností budou na svých finálních pozicích, slévání je úspěšně ukončeno.
  
  Celý tento postup zabere O(n), neboť "krátká" posloupnost má <n prvků a tedy její prvky se přesouvají nejvýše n-krát a každý prvek druhé posloupnosti se posouvá nejvýše jednou.
  (V případě, že "krátká" posloupnost v poli následuje jako druhá, použijeme analogický algoritmus začínající největším prvkem této "krátké" posloupnosti ("block merge backwards").)

1. Z předchozího tedy můžeme předpokládat, že každá ze vstupních posloupností má alespoň s=n prvků. Protože (s + 1)² > n , víme, že počet bloků velikosti s v poli je tedy nejvýše s + 2 .
   Pomocí porovnávání pravých konců posloupností najdeme s největších prvků, které budou ve vlastním algoritmu sloužit jako pomocná (auxiliary) oblast - označme tyto 2 části posloupností A a B s velikostmi po řadě s₁ a s₂ (s₁ + s₂ = s). Označme s₂ prvků nalevo od A jako C. Dále označme D nejkratší (třeba i prázdnou) skupinu prvků nalevo od B takovou, že pokud bychom D a B odstranili z druhé vstupní posloupnosti, její délka by byla celým násobkem čísla s.
   Nyní tedy můžeme na pole nahlížet jako na posloupnost bloků velikosti s - s vyjímkou prvního bloku o velikosti t₁ a posledního bloku (D B) o velikosti t₂, kde 0 < t₁  s a 0 < t₂ < 2s. (A C má velikost s.)
2. Vyměníme B a C, čímž dostaneme pomocnou oblast do 1 bloku.
   Nyní použijeme pomocnou oblast pro slití C a D (je-li některý prázdný, nic neděláme), výsledkem tohoto bude blok E o velikosti t₂ (stále na pravém konci pole). Nyní můžeme rozlišit 2 případy:
   1. Délka E > s - v tomto případě byly C i D neprázdné a tudíž všechny prvky od pozice s + 1 v E jsou libovolnému prvku nalevo od nich (i mimo E, ale s vyjímkou pomocné oblasti) a tedy v algoritmu se jimi vůbec nemusíme zabývat, až při závěrečném posunu pomocné oblasti se nám posunou, čímž se dostanou na své finální pozice. Tedy stačí se zabývat prvními s prvky - totožné s následujícím bodem.
   2. Pokud je délka E s a C i D byly neprázdné - pak tail(E ) libovolnému prvku mimo pomocnou oblast a tedy při třídění bloků s E nehýbeme a později ho normálně sléváme (že může být kratší nám nevadí).
      Byl-li některý z C, D prázdný, pak tail(E ) (a tedy i všechny ostatní prvky v E) může být menší než některý z prvků v předcházejících blocích (opět se nezabýváme prvky pomocné oblasti). To ovšem znamená, že všechny takovéto prvky se vyskytnou v 1. běhu v okamžiku, kdy E bude 2. běh - protože všechny takovéto prvky musí pocházet ze stejné vstupní posloupnosti a vzhledem k setřídění bloků (mimo E) dle jejich tail(...), nikde za prvním takovýmto prvkem, ale před head(E ), nedojde k přerušení tohoto běhu.
      Tedy s tímto blokem v algoritmu normálně pracuji, s vyjímkou fáze třídění bloků, kdy ho ignoruji - tedy nechám ho, kde je.
   Tedy E mi v algoritmu žádné problémy nezpůsobí.
3. Nyní nám tedy problémy může působit jen nejlevější blok (označme ho F) a to pouze za předpokladu, že jeho velikost je < s. Označme G nejlevější blok druhé vstupní posloupnosti. Použijeme t₁ nejpravějších prvků pomocné oblasti pro slití bloků F a G (stejným způsobem jako v algoritmu, tedy těch t₁ prvků pomocné oblasti se přestěhuje na začátek pole) - výsledné 2 bloky označme H a I. Jelikož jsme slili 2 bloky obsahující nejmenší prvky každé ze vstupních posloupností, můžeme H přesunout na začátek pole (tedy prohodit s tou částí pomocné oblasti, která zde do teď byla), kde již zůstane až do konce algoritmu - obsahuje totiž setříděné nejmenší prvky celého pole. Tímto se nám rovněž pomocná oblast spojí zpět do 1 bloku. S blokem I se bude v algoritmu pracovat jako s každým jiným.
   Nyní tedy vyměníme pomocnou oblast s prvním blokem následujícím za H, čímž jsme připraveni pro spuštění výše uvedené zjednodušené varianty algoritmu. (Obsah zpracovávané části sice nesplňuje zcela tam uvedené předpoklady, ale vše, co opravdu potřebujeme ano. Stačí přeskočit 1. krok algoritmu a dát si pozor na to, že počet bloků nemusí přesně odpovídat velikosti bloků.)

• Časová složitost výše uvedených úprav vstupních posloupností:
  1. krok lze triviálně provést v čase O(s), ve 2. kroku výměna i slití bloků zabere každé O(s) a 3. krok zabere rovněž O(s).
  Tedy celkem tyto úpravy zaberou čas O(s) a tedy nám časovou složitost algoritmu nezvýší.

Příklad úprav vstupních posloupností, aby na ně mohl být použit zjednodušený algoritmus

Poznámky k algoritmu:

• Rotaci - tedy prohození 2 částí pole (označme je X a Y) lze provést jednoduše v lineárním čase k počtu prvků těchto částí pole: Nejdříve obrátíme (tedy vyměníme 1. prvek s posledním, 2. prvek s předposledním atd.) X, pak obrátíme v celku X Y (tím se nám prvky z X dostanou na požadovanou pozici) a na závěr obrátíme Y (které před tímto krokem zabíralo začátek pole).
• Tento algoritmus (stejně jako Kronrodův) není stabilní (stable) - lze to snadno vypozorovat z výše uvedeného příkladu.
• Autoři algoritmu v závěru článku ukazují (nepříliš šťastným způsobem, neboť výměnu dvou prvků a jejich porovnání chápou jako stejně dlouho trvající operace, což nemusí být pravda, neboť prvky mohou mít složitější strukturu a pro jejich porovnání mi může stačit jen jejich část - klíč), že tento algoritmus by měl běžet v čase 3,5n + c pro nějakou konstantu c, zatímco libolný slévající algoritmus musí běžet v čase alespoň 2n - 1.
• Autoři rovněž ukazují empirické výsledky, podle kterých je tento algoritmus při 5000 prvcích zhruba dvakrát (a při 10⁶ prvcích asi 1,75-krát) pomalejší než rychlé slévání používající lineárně mnoho pomocné paměti. Pro detaily viz [Huang, Langston].

Shrnutí:

Zdroje a literatura:

• [Kronrod] M. A. Kronrod: An ordering algothm without a field of operation. (Dok. Akad. Nauk SSSR 186, str. 1256-8, 1969)
• [Knuth] D. E. Knuth: The art of computer programming - vol. 3: Sorting and searching. (Addison-Wesley, 1973)
  (Část týkající se slévání na místě v lin. čase: kapitola 5.2.4, příklad 18 - resp. jeho řešení na konci knihy.)
• [Huang, Langston] B. C. Huang, M. A. Langston: Practical In-Place Merging. (Communications of the ACM, March 1988, vol. 31, no. 3, str. 348 - 352)
• [Pardo] L. T. Pardo: Stable sorting and merging with optimal space and time bounds. (SIAM J. Comput. 6, str 351 - 372, 1977)
• [Huang, Langston 2] B. C. Huang, M. A. Langston: Fast stable merging and sorting in constant extra space (Computer Science Dep. Tech. Report CS-87-170, Washington State University, 1987)
• Některé další práce na toto téma lze najít v ResearchIndexu.