Mergesort je třídící algoritmus využívající metody rozděl a panuj. Dostane vstup, například posloupnost čísel, který rozdělí na dvě skoro stejné části. Ty nechá setřídit rekurzivně. Výsledné posloupnosti slije do jedné a tu vrátí jako setříděnou posloupnost.

Co znamená slít dvě setříděné posloupnosti $P_1$, $P_2$ do jedné? Cílem je vytvořit jednu posloupnost $P$, která obsahuje prvky obou předchozích posloupností a je setříděná. Menší prvek z počátečních (a nejmenších) prvků setříděných posloupností $P_1$, $P_2$ je určitě nejmenším prvkem výsledné posloupnosti $P$. Proto ho odtrhneme a přidáme na začátek $P$. Tím z $P_1$, $P_2$ vzniknou posloupnosti ${P_1}’$, ${P_2}’$. Pro ty můžeme celý postup zopakovat a tím dostaneme druhý nejmenší prvek $P$. Dalším opakováním postupně odtrháme všechny prvky obou setříděných posloupností $P_1$, $P_2$ a sestavujeme požadovanou posloupnost $P$.

Slévání si můžeme představovat trochu jako zip na oblečení. Dvě ozubené části zipu (setříděné posloupnosti) přiložíme k sobě a zapneme je jezdcem. Jezdec kontroluje, že do sebe ozubené části zapadají podle velikosti.

Klasická implementace Mergesortu pracuje se spojovým seznamem prvků. Pokud chceme mergesort implementovat v poli, tak se neobejdeme bez pomocného pole $\ARRAY{B}{\cdot}$, kam budeme ukládat mezivýsledky. Procedura Mergesort($l$, $p$) setřídí úsek pole $\ARRAY{A}{l .. p}$ mezi indexy $l$ a $p$. Pole $\ARRAY{A}{n}$ i pomocné pole $\ARRAY{B}{n}$ jsou globální proměnné.

Mergesort($l$, $p$)
	if $l < p$   then
		 $stred := \lfloor (l+p)/2 \rfloor$
		 Mergesort($l$, $stred$  )
		 Mergesort($stred+1,$   $p$ )
		 Merge($l$, $p$ )

Procedura Merge($l$, $p$) slije setříděné podposloupnosti $\ARRAY{A}{l .. stred}$ a $\ARRAY{A}{stred+1 .. p}$ do jedné setříděné posloupnosti $\ARRAY{A}{l .. p}$. Pro ukládání mezivýsledků potřebuje pomocné pole $\ARRAY{B}{l .. p}$. Procedura Merge má časovou složitost $\OO(m)$, kde $m$ je délka výsledné posloupnosti.

Merge($l$, $p$ )
	$stred := \lfloor (l+p)/2 \rfloor$
	$i:=l$        	{Index na začátek první setříděné posloupnosti. }
	$j:=stred+1$   	{Index na začátek druhé setříděné posloupnosti.}
	$k:=l$        	{Index do pole $\ARRAY{B}{\cdot},$   kam zapisujeme výsledek.}
	while $k\leq p$    do
		if  $i > stred$     then       	{První posloupnost došla.}
			 $\ARRAY{B}{k} := \ARRAY{A}{j}$
			 $j:=j+1$
		else if  $j > p$  then       	{Druhá posloupnost došla.}
			 $\ARRAY{B}{k} := \ARRAY{A}{i}$
			 $i:=i+1$
		else if  $\ARRAY{A}{i} < \ARRAY{A}{j}$   then       {Žádná posloupnost nedošla.}
			 $\ARRAY{B}{k} := \ARRAY{A}{i}$
			 $i:=i+1$
		else
			 $\ARRAY{B}{k} := \ARRAY{A}{j}$
			 $j:=j+1$
		 $k:=k+1$
	for $k:=l$ to $p$   do      {Kopírování výsledků z  $\ARRAY{B}{l .. p}$    do  $\ARRAY{A}{l .. p}$ }
		 $\ARRAY{A}{k} := \ARRAY{B}{i}$

Časová složitost Mergesort je určena rekurencí $T(n)=2T(n/2)+\OO(n)$, protože dvakrát řešíme podúlohu poloviční velikosti a jednou sléváme výsledky dohromady.

Následující obrázek ilustruje průběh algoritmu a slévání jednotlivých částí. Strom rekurze máme nakreslený vzhůru nohama, protože se algoritmus nejprve zanoří, co nejhlouběji to jde, a teprve při zpáteční cestě provádí slévání podposloupností (úseků pole). Pro lidi je přirozenější ta zpáteční cesta, na které se něco děje.


Strom rekurze má hloubku nejvýše $\lceil \log n \rceil$, protože při každém zavolání Mergesort rozdělíme posloupnost v půlce. Na $k$-té hladině1 se slévají dvě posloupnosti délky $n/2^{k+1}$ do posloupnosti délky $n/2^{k}$. Těchto slévání se na $k$-té hladině vykoná $2^k$. Proto je celková práce na $k$-té hladině rovna $\OO(n)$. Z toho dostáváme časovou složitost algoritmu mergesort $\OO(n\log n)$.

Poznámka k implementaci: Na konci každého volání Merge kopírujeme výsledky z pomocného pole $\ARRAY{B}{\cdot}$ do pole $\ARRAY{A}{\cdot}$. Tomu se můžeme vyhnout tak, že budeme při rekurzivním volání Mergesortu střídat význam pole $\ARRAY{A}{\cdot}$ a $\ARRAY{B}{\cdot}$. Na sudých hladinách dostane Merge posloupnost v poli $\ARRAY{B}{\cdot}$ a vytvoří setříděnou posloupnost do pole $\ARRAY{A}{\cdot}$ a v lichých hladinách naopak. Prohazování můžeme zrealizovat tak, že funkci Merge předáme i ukazatele na tyto pole a při rekurzivním zavolání ukazatele prohodíme. Mohlo by se stát, že střídání polí po hladinách vyjde tak, že budeme v poslední hladině chtít slévat položky z $\ARRAY{B}{\cdot}$ do pole $\ARRAY{A}{\cdot}$. Proto na začátku celého algoritmu nakopírujeme celý vstup z $\ARRAY{A}{\cdot}$ i do pole $\ARRAY{B}{\cdot}$.