Lomituslajittelu

Lomituslajittelu (limityslajittelu, lomitusjärjestäminen, "Merge sort") on asymptoottiselta suoritusajaltaan tehokas (Θ(formula_1 log formula_1)) ja vakaa lajittelumenetelmä, mutta vaatii tavallisella vektorimuotoisella taulukolla lisämuistia (O(n)). Erityisen hyödyllinen se on kuitenkin linkitettyjen listojen järjestämiseen, jolloin lisämuistia ei tarvita. Se toimii pääpiirteissään seuraavasti:
Esimerkkitoteutus.
Ohessa pseudokielinen toteutus 'tavalliselle' taulukolle:
 algoritmi Lomituslajittelu(taulukko t, lisätaulukko l, kokonaisluku alku, kokonaisluku loppu)
 if alku &gt;= loppu then // Korkeintaan 1 alkio, ei tarvitse järjestää
 lopeta algoritmin suoritus
 else if alku + 1 = loppu then // 2 alkiota, helppo järjestää
 if t[alku] &lt; t[loppu] then
 Vaihda alkioiden t[alku] ja t[loppu] arvot keskenään
 end if
 else // Järjestetään puolikkaat rekursiivisesti ja lomitetaan
 väli := (alku + loppu)/2 // Katkaisukohta (pyöristetään alaspäin)
 Lomituslajittelu(t,l,alku,väli) // Järjestetään puolikkaat
 Lomituslajittelu(t,l,väli+1,loppu)
 // Lomitetaan lisätaulukkoon ja kopioidaan alkuperäiseen taulukkoon
 i := alku // 1. puolikkaan indeksi
 j := väli + 1 // 2. puolikkaan indeksi
 k := alku // Lomituksen indeksi
 while k ⇐ loppu // Käsitellään kaikki välin alkiot
 // Vertaillaan kummankin puolikkaan suurinta jäljellä olevaa arvoa
 // ja sijoitetaan suurempi lomitukseen seuraavaksi
 // Jos jommassakummassa puolikkaassa ei ole alkioita jäljellä,
 // siirretään kaikki toisen puolikkaan alkiot
 if i &gt; väli then // 1. puolikkaassa ei alkioita
 while j ⇐ loppu
 l[k] := t[j]
 k := k + 1
 j := j + 1
 end while
 else if j &gt; loppu // 2. puolikkaassa ei alkioita
 while i ⇐ väli
 l[k] := t[i]
 k := k + 1
 i := i + 1
 end while
 else // Molemmissa puolikkaissa alkioita
 if t[i] &gt; t[j] then
 l[k] := t[i]
 i := i+1
 else
 l[k] := t[j]
 j := j+1
 end if
 k := k + 1
 end if
 end while
 // Kopioidaan lomitus alkuperäiseen taulukkoon
 for a = alku to loppu
 t[a] = l[a]
 end for
 end if
 end
 (Huom. lisätaulukon l on oltava vähintään yhtä suuri kuin taulukon t.
 Algoritmi järjestää kaikki parametrien 'alku' ja 'loppu' rajaamilla
 indekseillä olevat alkiot, koko taulukon järjestämiseen on
 algoritmia kutsuttava komennolla
 Lomituslajittelu(t,l,1,taulukon t alkioiden lukumäärä) )
Esimerkkitoteus C-kielellä.
Lajittelee yhteen suuntaan linkitetyn listan nousevaan järjestykseen, ”cmp” vertailufunktion osoite, ”t_node” typedef linketetyn listan elementin toteuttavalle rakenteelle (struct). 
void mergesort(t_node **a, int (*cmp)(void *b, void *c)) {
 t_node *t;
 t_node *u;
 if (a != NULL &amp;&amp; *a != NULL &amp;&amp; (*a)-&gt;next != NULL) {
 u = split_list(*a);
 mergesort(a, cmp);
 mergesort(&amp;u, cmp);
 t = *a;
 if ((*cmp)(t, u) &gt; 0)
 *a = u;
 merge_lists(t, u, cmp);
int list_size(t_node *a) {
 register int i;
 i = 0;
 while (a != NULL) {
 a = a-&gt;next;
 i++;
 return (i);
t_node *split_list(t_node *a) {
 register int i;
 register int size;
 t_node *u;
 size = list_size(a);
 i = 0;
 while (i &lt; size / 2 - 1) {
 a = a-&gt;next;
 i++;
 u = a-&gt;next;
 a-&gt;next = NULL;
 return (u);
void roll_merge(t_node **r, t_node **v) {
 (*v)-&gt;next = *r;
 *v = (*v)-&gt;next;
 *r = (*r)-&gt;next;
void merge_lists(t_node *t, t_node *u, int (*cmp)(void *b, void *c)) {
 t_node *v;
 v = t;
 if ((*cmp)(t, u) &gt; 0) {
 v = u;
 u = u-&gt;next;
 } else
 t = t-&gt;next;
 while (t != NULL &amp;&amp; u != NULL) {
 if ((*cmp)(t, u) &gt; 0)
 roll_merge(&amp;u, &amp;v);
 else
 roll_merge(&amp;t, &amp;v);
 if (u == NULL)
 v-&gt;next = t;
 else
 v-&gt;next = u;