Jsort
JSort je algoritam koji radi u mestu i dva puta koristi hip da donekle sortira niz, a onda primeni sortiranje umetanjem. Jsort se pripisuje Jason Morrison-u.[1]
Prvim prolaskom kroz niz, kreira se hip sa najmanjim elementom u korenu, koji je prvi član niza. Drugi prolazak kroz niz radi obrnuto, kreira hip sa najvećim elementom u korenu, koji je poslednji element u nizu. Donekle sortiran niz se dalje sortira umetanjem. S obzirom da se sortiranje vrši umetanjem, dva prolaska služe da se kreira hip, što dovodi do uštede.
Kreiranjem hipa, brzo se dobije delimično sortiran niz, jer se elementi mogu pomeriti čak za polovinu dužine niza. Velika je šansa da su elementi blizu korena sortirani jer se mali broj elemenata međusobno poredi. Što se više odaljavamo od korena, sve je manja šansa da su elementi sortirani jer se ne porede jedni sa drugima već samo sa roditeljima. Stoga, elementi koji su listovi su najverovatnije nesortirani, što može dovesti do toga da sortiranje umetanjem dugo traje.
Drugi prolazak obrće hip i stavlja koren na poslednje mesto u nizu. To takodje menja logiku hipa, tako da je u korenu najveći element. Redosled elemenata u drugom prolasku je i dalje isti, manji blizu prve pozicije u nizu, veliki blizu poslednje, ali drugi prolazak radi sa onim elementima sa kojima nije prvi prolazak (onima koji su pri kraju niza). Ova dva prolaska zajedno delimično sortiraju niz. Konačno, sortiranje umetanjem može da se izvrši relativno brzo. Složenost je i dalje O(n2).