Lomituslajittelu

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

1. Jaa taulukko kahteen yhtä suureen osataulukkoon
2. Järjestä osataulukot rekursiivisesti
3. 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] < 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 > 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-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 && *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;
}