Implementace Javascript Array.sort?

Který algoritmus dělá JavaScript Array#sort() využití funkce? Chápu, že k provádění různých druhů může být zapotřebí nejrůznějších argumentů a funkcí, prostě mě zajímá, jaký algoritmus používá vanilkové řazení.

Odpověď

Právě jsem se podíval na zdroj WebKit (Chrome, Safari…). V závislosti na typu pole se používají různé způsoby řazení:

Číselná pole (nebo pole primitivního typu) se třídí pomocí funkce standardní knihovny C++ std::qsort který implementuje nějakou variaci quicksortu (obvykle introsort).

Souvislá pole nenumerického typu jsou stringována a tříděna pomocí mergesort, pokud je k dispozici (pro získání stabilního řazení) nebo qsort pokud není k dispozici žádné řazení sloučení.

Pro jiné typy (nesouvislá pole a pravděpodobně pro asociativní pole) WebKit používá buď výběrové řazení (které nazývají „min“ řazení), nebo v některých případech třídí pomocí stromu AVL. Zde je bohužel dokumentace poněkud vágní, takže byste museli sledovat cesty kódu, abyste skutečně viděli, pro které typy se používá metoda řazení.

A pak jsou tu skvosty jako tento komentář:

// FIXME: Since we sort by string value, a fast algorithm might be to use a
// radix sort. That would be O(N) rather than O(N log N).

– Doufejme, že kdokoli to skutečně „opraví“, rozumí asymptotickému běhovému prostředí lépe než autor tohoto komentáře a uvědomí si, že radix sort má poněkud složitější popis běhového prostředí než jednoduše O(N).

(Děkujeme phsource za upozornění na chybu v původní odpovědi.)