Lomituslajittelu

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

Luokka:Lajittelualgoritmit

no:Sorteringsalgoritme#Flettesortering