Lomituslajittelualgoritmin analyysi
Merkitään lomituslajittelualgoritmin n alkion taulukon A[1..n] lajitteluun tarvitsemaa aikaa T(n):llä. Oletetaan yksinkertaisuuden vuoksi, että n on jokin kakkosen potenssi ja että kunkin ”alkeisoperaation” kesto on 1 aikayksikkö.
Helposti nähdään, että taulukon A[1..n] puolittamiseen ja lajiteltujen puolikastaulukoiden yhdistämiseen kuluva aika on O(n) yksikköä. Ajatellaan yksinkertaisuuden vuoksi, että tämä aika on tasan n yksikköä.
Koko algoritmin suoritusaikaa kuvaa tällöin rekursioyhtälö
T(1) = 1,
T(n) = 2T(n/2) + n, kun n = 2k, k ³ 1.
Voidaan osoittaa (tai tarkastaa esim. induktiolla), että tämän rekursioyhtälön ratkaisu on
Lomituslajittelun aikavaativuus ei siis ole aivan lineaarinen, vaan kertaluokkaa O(n log2 n). Kuten nähtiin, tämä on kuitenkin huomattavasti parempi saavutus kuin valintalajittelun O(n2).