MSDradixlajitteluun

MSD-radixlajitteluun on ei-vertaileva lajittelualgoritmi, joka järjestää avaimet eniten merkityksellisen sijan mukaan ensin. Ajatus on jakaa avaimet current-sijalla kunkin mahdollisen digit-arvon perusteella ämpäreihin ja toistaa prosessin seuraavalla, vähemmän merkitsevällä sijalla. Jos avaimet ovat merkkijonoja, digitaaliset arvot voivat määräytyä käyttää ASCII/Unicode-merkkijonoja tai laajempaa merkistökokoa. Prosessi on usein rekursiivinen: jokainen ämpäri lajitellaan uudelleen seuraavalla sijalla, kunnes kaikki sijat on käsitelty tai ämpäri sisältää vain vähän avaimia.

Käytännössä MSD-lajittelussa verrataan ja jaotellaan digitaalien mukaan uudelleen jokaisessa vaiheessa, jolloin avaimet, joilla on sama prefix, pysyvät peräkkäin oikeassa järjestyksessä. Tämä tekee lajittelusta vakaata, mikä tarkoittaa, että saman prefixin avaimet säilyttävät alkuperäisen järjestyksensä muiden avainten suhteen.

Monimutkaisuus ja muistivaatimukset: MSD-radixlajittelun aikavaativuus on noin O(nk), missä n on avaimien määrä ja k on avaimien merkkien määrä, ja se saa aikaan lisätilan ämpäreille sekä mahdolliselle rekursiokaarelle. Parhaissa oloissa suoritusteho on hyvä, erityisesti suurissa joukkoissa, joissa avaimet jakautuvat tasaisesti. Muutoksena LSD-radixlajitteluun (Least Significant Digit) käsitellään digitoita pienimmästä suurimpaan, usein ilman rekursiota, ja sen sovellus poikkeaa tapauksittain.

Käyttökohteet: MSD-lajittelua käytetään etenkin suurien merkkijonotunnisteiden ja kiinteäpituisia avaimia sisältävissä kokoelmissa sekä ulkoisessa lajittelussa, jossa muistia on rajallisesti käytettävissä ja avaimet ovat pitkiä. MSD ja LSD ovat yleisiä radix-sort-tyyppejä, joilla on omat etunsa ja toteutusvalintansa.