Mise en œuvre de JavaScript Array.sort ?

Question

Algorithme qui fait le code JavaScript `` fonction utilisation ? Je comprends qu’il peut prendre toutes sortes d’arguments et de fonctions pour effectuer différents types de toutes sortes, je suis tout simplement intéressé par un algorithme qui utilise le type de vanille.

Answer 1

J'ai juste eu un coup d'oeil à la WebKit (Chrome, Safari,...) de la source. En fonction du type de tableau, les différentes sortes de méthodes sont utilisées:

Des tableaux numériques (ou des tableaux de type primitif) sont triés à l'aide de la norme C++ de la bibliothèque de fonction std::qsort qui met en œuvre une certaine variation de quicksort (généralement introsort).

Contigus des tableaux de non numériques sont stringified et triés à l'aide de mergesort, si disponible (pour obtenir un tri stable) ou qsort si pas de fusion de tri est disponible.

Pour les autres types (non contigus tableaux et sans doute pour les tableaux associatifs) WebKit utilise soit de tri de la sélection (qu'ils appellent "min" tri) ou, dans certains cas, il trie par l'intermédiaire d'un arbre AVL. Malheureusement, la documentation ici, c'est plutôt vague, de sorte que vous auriez à la trace les chemins de code pour voir pour qui de types de méthode de tri est utilisé.

Et puis il y a des perles comme ce commentaire:

// 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).

– Espérons juste que celui qui fait "résout" ce qui a une meilleure compréhension de l'asymptotique d'exécution que l'auteur de ce commentaire, et se rend compte que radix tri a un peu plus complexe runtime description que de simplement O(N).

(Merci à phsource pour souligner l'erreur dans la réponse originale à cette question.)

Answer 2

Si vous regardez ce bug 224128, il semble que MergeSort est utilisé par Mozilla.

Answer 3

Après quelques recherches plus, semble-t-il, pour Mozilla/Firefox, que Array.sort() utilise des algorithmes. Voir le code ici.

Answer 4

Je pense que cela dépendrait quelle implémentation de navigateur, vous êtes en se référant à.

Chaque type de navigateur a son propre moteur mise en œuvre javascript, donc il dépend. Vous pouvez consulter le code source repos pour Mozilla et Webkit/Khtml pour des implémentations différentes.

IE est fermé de source cependant, donc vous devrez peut-être demander à quelqu'un chez microsoft.