Algoritam spajanja
Algoritmi spajanja su grupe algoritama koji rade sekvencijalno sa više sortiranih nizova i obično proizvode više sortiranih nizova kao izlaz. Upotreba algoritma je opala zbog velikih RAM memorija i mnoge aplikacije koje koriste ovaj algoritam imaju brže alternative kada se koristi RAM.

Opšti algoritam spajanja ima niz pokazivača p0..n koji pokazuju na pozicije u grupi nizova L0..n. Inicijalno oni pokazuju na prvi element svakog niza. Algoritam glasi:

Sve dok neki od pokazivača p0..n pokazuje na podatke u nizovima L0..n:
 uradi nešto sa podacima
 pronađi koji od pokazivača pokazuje na najmanji element; preusmeri pokazivač na sledeći element

Analiza 
Za rad ovih algoritama obično je potrebno vreme proporcionalno sumi dužina nizova. Oni algoritmi koji istovremeno rade sa velikim brojem nizova množe sumu dužina nizova sa vremenom da bi pronašli pokazivač na najmanji element, što se može postići pomoću reda sa prioritetom koji je baziran na hipu za O(log n) vremena, za O(m log n) vremena, gde je n broj nizova koji se spajaju a m je suma dužina nizova. Kada se spajaju dva niza dužine m, donja granica poređenja u najgorem slučaju je 2m − 1.

Klasično spajanje (koje se koristi u sortiranju spajanjem) kao izlaz vraća najmanji element; ako na ulazu ima sortirane nizove, kao izlaz vraća sortirani niz koji sadrži sortirane elemente bilo kog niza sa ulaza, i to čini u vremenu proporcionalnom sumi dužina nizova sa ulaza.

Jezička podrška 

Standardna C++ biblioteka sadrži funkciju std::merge, koja spaja dva sortirana niza i std::inplace_merge, koja spaja dva uzastopno sortirana niza u mestu. Klasa std::list ima svoj metod merge() koji sebi pripaja drugu listu. Tipovi spojenih elemenata moraju da sadrže operator manje (<) ili se mora obezbediti proizvoljan komparator.

Standardna Python biblioteka (od verzije 2.6) takođe ima funkciju merge() u heapq modulu, koja uzima više sortiranih nizova i spaja ih u jedan.

Paralelno spajanje 
Kod multiprogramiranja, nizovi sortiranih vrednosti se mogu efikasno spojiti pomoću problema svih najbližih najmanjih vrednosti.

Paralelno spajanje se takođe može implementirati pomoću zavadi-pa-vladaj algoritma. Ovaj algoritam dobro radi kada se iskoristi sa brzim sekvencijalnim spajanjem kao bazni slučaj spajanja malih nizova. Implementacija pomoću Intelovih Threading Building Blocks (TBB) i Majkrosoftove Parallel Pattern Library (PPL) koja radi sa procesorima sa više jezgara se dobro pokazala u praksi.

Reference

Literatura 
  Pages 158-160 of section 5.2.4: Sorting by Merging. Section 5.3.2: Minimum-Comparison Merging. pp. 197-207.
 

Алгоритми сортирања
Algoritmi spajanja su grupe algoritama koji rade sekvencijalno sa više sortiranih nizova i obično proizvode više sortiranih nizova kao izlaz . Upotreba algoritma je opala zbog velikih RAM memorija i mnoge aplikacije koje koriste ovaj algoritam imaju brže alternative kada se koristi RAM . Opšti algoritam spajanja ima niz pokazivača p0..n koji pokazuju na pozicije u grupi nizova L0..n . Inicijalno oni pokazuju na prvi element svakog niza . Algoritam glasi : Sve dok neki od pokazivača p0..n pokazuje na podatke u nizovima L0..n : uradi nešto sa podacima pronađi koji od pokazivača pokazuje na najmanji element ; preusmeri pokazivač na sledeći element Analiza Za rad ovih algoritama obično je potrebno vreme proporcionalno sumi dužina nizova . Oni algoritmi koji istovremeno rade sa velikim brojem nizova množe sumu dužina nizova sa vremenom da bi pronašli pokazivač na najmanji element , što se može postići pomoću reda sa prioritetom koji je baziran na hipu za O( log n ) vremena , za O( m log n ) vremena , gde je n broj nizova koji se spajaju a m je suma dužina nizova . Kada se spajaju dva niza dužine m , donja granica poređenja u najgorem slučaju je − 1. Klasično spajanje ( koje se koristi u sortiranju spajanjem ) kao izlaz vraća najmanji element ; ako na ulazu ima sortirane nizove , kao izlaz vraća sortirani niz koji sadrži sortirane elemente bilo kog niza sa ulaza , i to čini u vremenu proporcionalnom sumi dužina nizova sa ulaza . Jezička podrška Standardna C++ biblioteka sadrži funkciju std::merge , koja spaja dva sortirana niza i std::inplace_merge , koja spaja dva uzastopno sortirana niza u mestu . Klasa std::list ima svoj metod merge ( ) koji sebi pripaja drugu listu . Tipovi spojenih elemenata moraju da sadrže operator manje ( < ) ili se mora obezbediti proizvoljan komparator . Standardna Python biblioteka ( od verzije6 ) takođe ima funkciju merge ( ) u heapq modulu , koja uzima više sortiranih nizova i spaja ih u jedan . Paralelno spajanje Kod multiprogramiranja , nizovi sortiranih vrednosti se mogu efikasno spojiti pomoću problema svih najbližih najmanjih vrednosti . Paralelno spajanje se takođe može implementirati pomoću zavadi-pa-vladaj algoritma . Ovaj algoritam dobro radi kada se iskoristi sa brzim sekvencijalnim spajanjem kao bazni slučaj spajanja malih nizova . Implementacija pomoću Intelovih Threading Building Blocks ( TBB ) i Majkrosoftove Parallel Pattern Library ( PPL ) koja radi sa procesorima sa više jezgara se dobro pokazala u praksi . Reference Literatura Pagesof section2.4 : Sorting by Merging . Section3.2 : Minimum-Comparison Merging. pp . Алгоритми сортирања