Lomituslajittelu

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.
void Mergesort(struct lista **a, int (*cmp)(void *a, void *b)) {
    if(a) {
        struct lista *b1=(*a);
        int c=1, i=0;
        while(b1->next)
            b1=b1->next, c++;
        if(c>1) {
    b1=(*a);
    for(i=1; i<c/2; i++)
        b1=b1->next;
            struct lista *b2 = b1->next, *b3;
    b1->next=NULL;
            Mergesort(a, cmp);
    Mergesort(&b2, cmp);
    b3=(*a);
    while(b2) {
        if(cmp(b3,b2)>0) {
    if(b3==(*a)) {
         (*a)=b2;
         b2=b2->next;
         (*a)->next=b3;
    }
    else {
        struct lista *b4 = (*a);
        while(b4->next != b3)
                            b4=b4->next;
        b4->next=b2;
        b2=b2->next;
        b4->next->next=b3;
    }
continue;
}
        else {
    while(b3->next && cmp(b3->next,b2)<0)
        b3=b3->next;
    if(!b3->next) {
        b3->next=b2;
        break;
    }
    else {
        struct lista *b5 = b3->next;
        b3->next=b2;
        b2=b2->next;
        b3->next->next=b5;
        continue;
    }
                }
    break;
    }
        }
    }}