Nopea lajittelu on sisäinen algoritmi, joka perustuu hajota ja hallitse -strategiaan. Tässä:

• Elementtijoukko jaetaan osiin toistuvasti, kunnes sitä ei voida enää jakaa.
• Se tunnetaan myös nimellä osionvaihtolajittelu .
• Se käyttää avainelementtiä (pivotia) elementtien osiointiin.
• Yksi vasen osio sisältää kaikki ne elementit, jotka ovat pienempiä kuin pivot ja yksi oikea osio sisältää kaikki elementit, jotka ovat suurempia kuin avainelementti.

Yhdistä lajittelu on ulkoinen algoritmi ja perustuu hajota ja hallitse -strategiaan. Tässä:

• Elementit jaetaan kahteen alitaulukkoon (n/2) uudestaan ​​ja uudestaan, kunnes jäljellä on vain yksi elementti.
• Yhdistämislajittelu käyttää lisätallennustilaa aputaulukon lajitteluun.
• Yhdistämislajittelu käyttää kolmea taulukkoa, joista kahta käytetään kummankin puolikkaan tallentamiseen ja kolmatta ulkoista lopullista lajiteltua listaa käytetään yhdistämällä kaksi muuta ja jokainen taulukko lajitellaan sitten rekursiivisesti.
• Lopulta kaikki alitaulukot yhdistetään, jotta siitä tulee taulukon elementtikoko 'n'.

Pikalajittelu vs yhdistämislajittelu

Elementtien osiointi taulukossa: Yhdistämislajittelussa taulukko jaetaan vain kahteen puolikkaaseen (eli n/2). kun taas nopeassa lajittelussa taulukko jaetaan mihin tahansa suhteeseen. Ei ole pakko jakaa elementtijoukkoa yhtä suuriin osiin nopeassa lajittelussa. Pahimman tapauksen monimutkaisuus: Pikalajittelun pahimman tapauksen monimutkaisuus on O(n^2), koska pahimmassa kunnossa tarvitaan paljon vertailuja. kun taas yhdistämislajittelussa huonoimmalla ja keskimääräisellä tapauksella on samat kompleksisuudet O(n log n). Käyttö tietojoukkojen kanssa: Yhdistämislajittelu voi toimia hyvin kaikentyyppisissä tietojoukoissa niiden koosta riippumatta (joko suuri tai pieni). kun taas nopea lajittelu ei toimi hyvin suurten tietojoukkojen kanssa. Lisätallennustilan tarve : Yhdistelmälajittelu ei ole käytössä, koska se vaatii lisämuistitilaa aputaulukoiden tallentamiseen. kun taas nopea lajittelu on paikallaan, koska se ei vaadi ylimääräistä tallennustilaa. Tehokkuus: Yhdistämislajittelu on tehokkaampaa ja toimii nopeammin kuin nopea lajittelu, jos taulukkokoko tai tietojoukkoja on suurempi. kun taas pikalajittelu on tehokkaampaa ja toimii nopeammin kuin yhdistämislajittelu, jos taulukkokoko tai tietojoukkoja on pienempi. Lajittelutapa: Pikalajittelu on sisäinen lajittelumenetelmä, jossa tiedot lajitellaan päämuistissa. kun taas yhdistämislajittelu on ulkoinen lajittelumenetelmä, jossa lajiteltavaa dataa ei voida majoittaa muistiin ja lajitteluun tarvitaan apumuisti. Vakaus : Yhdistämislajittelu on vakaa, koska kaksi samanarvoista elementtiä näkyvät samassa järjestyksessä lajitetussa lähdössä kuin ne olivat syötetyssä lajittelemattomassa taulukossa. kun taas pikalajittelu on epävakaa tässä skenaariossa. Mutta se voidaan tehdä vakaaksi käyttämällä joitain muutoksia koodiin. Suositeltu: Pikalajittelu on suositeltava taulukoille. kun taas Yhdistä lajittelu on suositeltava linkitetyissä luetteloissa. Viittauspaikka: Quicksortilla on hyvä välimuistipaikka, mikä tekee pikalajittelusta nopeamman kuin yhdistämislajittelun (monissa tapauksissa kuten virtuaalimuistiympäristössä).