Algoritmus řazení slučováním je komplementární k řazení dělení. Namísto dělení posloupnosti je algoritmus řazení slučováním založen na slučování seřazených podposloupností.
Prvky uspořádaných polí a a b seřadíme sloučením do pole c jejich postupným procházením od začátku a vybráním menšího prvku. Přijdeme-li na konec jednoho z nich překopírujeme zbývající prvky druhého (obr.).
Naším úkolem je ovšem seřadit prvky jednoho pole. Předpokládejme, že v poli a jsou dva vzestupně seřazené úseky. Seřadit je algoritmem řazení slučováním můžeme tak, že vytvoříme pole b s bitonickou posloupností prvků pole a, tj. druhý úsek bude seřazen sestupně.
Je-li posloupnost a = { 1,3,7,2,6 } potom odpovídající bitonická posloupnost je b = { 1,3,7,6,2 }.
V poli a pak zpátky z pole b vytvoříme seřazenou posloupnost původních úseků tak, že pole budeme procházet indexy i a j z obou konců a menší z prvků vložíme do pole a (obr.).
Je-li v poli a první seřazený úsek v prvcích a[l] až a[s] a druhý v prvcích a[s+1] až a[p] a pole, ve kterém vytvoříme bitonickou posloupnost nazveme pom, potom seřazení jeho prvků sloučením vykoná metoda slouceni( ) na obr.. V prvním cyklu for do pole pom zkopírujeme první úsek pole a tak, aby na konci kopírovaní proměnná i měla hodnotu l. V druhém cyklu for zkopírujeme druhý úsek v obráceném pořadí tak, aby proměnná j měla po zkopírovaní hodnotu p. Ve třetím cyklu for tak můžeme přímo začít slučování obou úseků zpátky do pole a.
Nyní můžeme libovolné pole seřadit tak, že ho rozdělíme na půlky, rekurzivně je seřadíme a potom je sloučíme, což je základní algoritmus řazení slučováním. Základní případ je opět prázdný nebo jednoprvkový úsek pole. Algoritmus řazení slučováním je na obr.. Program pro řazení slučováním je na obr.
. Průběh slučování řazením je na obr.
.
Uvažujme, že velikost řazeného pole je n = 2k . Jeho výsledné seřazení vznikne sloučením dvou polí o velikosti n /2, což vyžaduje n porovnání. Každé z nich vzniklo sloučením dvou polí o velikosti n /4, což vyžadovalo 2.(n /2) = n porovnání. Tak postupujeme až k jednoprvkovým polím. Počet porovnání tedy je n log2 n. Tento výsledek platí také obecně.
Vidíme, že obdobně jako pro řazení haldou, algoritmus řazení slučováním je n log2 n pro libovolnou posloupnost n prvků.
Uvedený algoritmus potřebuje navíc paměť úměrnou n.