Lomituslajittelu

**Lomituslajittelu** (limityslajittelu, lomitusjärjestäminen, *Merge sort*) on asymptoottiselta suoritusajaltaan tehokas (Θ(n log n)) 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:

# Jaa taulukko kahteen yhtä suureen osataulukkoon
# Järjestä osataulukot rekursiivisesti
# Lomita järjestyksessä olevat osataulukot takaisin yhdeksi järjestyksessä olevaksi taulukoksi

## Esimerkkitoteutus
Ohessa pseudokielinen toteutus 'tavalliselle' taulukolle:

  algoritmi Lomituslajittelu(taulukko t, lisätaulukko l, kokonaisluku alku, kokonaisluku loppu)
 
      if alku >= 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]  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 > 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] > 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 (ohjelmointikieli)|C-kielellä]]

Lajittelee yhteen suuntaan linkitetyn listan nousevaan järjestykseen, ”cmp” vertailufunktion osoite, ”t_node” typedef linketetyn listan elementin toteuttavalle rakenteelle (struct). 


```c
void mergesort(t_node **a, int (*cmp)(void *b, void *c)) {
    t_node          *t;
    t_node          *u;

    if (a != NULL && *a != NULL && (*a)->next != NULL) {
        u = split_list(*a);
        mergesort(a, cmp);
        mergesort(&u, cmp);
        t = *a;
        if ((*cmp)(t, u) > 0)
            *a = u;
        merge_lists(t, u, cmp);
    }
}

int list_size(t_node *a) {
    register int i;

    i = 0;
    while (a != NULL) {
        a = a->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 < size / 2 - 1) {
        a = a->next;
        i++;
    }
    u = a->next;
    a->next = NULL;
    return (u);
}

void roll_merge(t_node **r, t_node **v) {
    (*v)->next = *r;
    *v = (*v)->next;
    *r = (*r)->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) > 0) {
        v = u;
        u = u->next;
    } else
        t = t->next;
    while (t != NULL && u != NULL) {
        if ((*cmp)(t, u) > 0)
            roll_merge(&u, &v);
        else
            roll_merge(&t, &v);
    }
    if (u == NULL)
        v->next = t;
    else
        v->next = u;
}
```