Јсорт
ЈСорт је алгоритам који ради у месту и два пута користи хип да донекле сортира низ, а онда примени сортирање уметањем. Јсорт се приписује Јасон Моррисон-у.[1]
Првим проласком кроз низ, креира се хип са најмањим елементом у корену, који је први члан низа. Други пролазак кроз низ ради обрнуто, креира хип са највећим елементом у корену, који је последњи елемент у низу. Донекле сортиран низ се даље сортира уметањем. С обзиром да се сортирање врши уметањем, два проласка служе да се креира хип, што доводи до уштеде.
Креирањем хипа, брзо се добије делимично сортиран низ, јер се елементи могу померити чак за половину дужине низа. Велика је шанса да су елементи близу корена сортирани јер се мали број елемената међусобно пореди. Што се више одаљавамо од корена, све је мања шанса да су елементи сортирани јер се не пореде једни са другима већ само са родитељима. Стога, елементи који су листови су највероватније несортирани, што може довести до тога да сортирање уметањем дуго траје.
Други пролазак обрће хип и ставља корен на последње место у низу. То такодје мења логику хипа, тако да је у корену највећи елемент. Редослед елемената у другом проласку је и даље исти, мањи близу прве позиције у низу, велики близу последње, али други пролазак ради са оним елементима са којима није први пролазак (онима који су при крају низа). Ова два проласка заједно делимично сортирају низ. Коначно, сортирање уметањем може да се изврши релативно брзо. Сложеност је и даље О(н2).