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:

1. Jaa taulukko kahteen yhtä suureen osataulukkoon
2. Järjestä osataulukot rekursiivisesti
3. Lomita järjestyksessä olevat osataulukot takaisin yhdeksi järjestyksessä olevaksi taulukoksi

Kahdeksan luvun lajittelu.

Seitsemän luvun lajittelu ryhmiteltynä kaavioksi.

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;
}