Lomituslajittelualgoritmi
Toinen menetelmä lukujoukon järjestämiseen on seuraava ”rekursiivinen” (osittava) algoritmi:
Olkoot lajiteltavat luvut talletettu taulukon A alkioiksi A[1] ... A[n]. Oletetaan yksinkertaisuuden vuoksi että luku n on muotoa 2k jollakin k = 0,1,2,...
1. Jos n = 1, taulukossa A on vain yksi alkio, eikä mitään tarvitse tehdä.
2. Jos n ³ 1, jaa taulukko A kahteen yhtäsuureen puolikastalukkoon,
A’ = A[1..n/2] ja A’’ = A[n/2+1..n] ja käytä tässä kuvattua menetelmää
ensin kummankin puolikkaan lajitteluun.
3. Kun puolikastaulukot A’ ja A’’ on lajiteltu, lomita niiden alkiot yhteen
taulukkoon A poimimalla alkioita kummastakin vuorollaan suuruus-
järjestyksessä.
Esimerkiksi taulukon A = [3 1 4 2] lajittelu tällä menetelmällä sujuu seuraavasti: