What Sorting Algorithm Does JavaScript\'s `Array.sort()` Use?

Algorithm Used by JavaScript Array.sort() Function

The JavaScript Array#sort() function is a versatile sorting mechanism that supports various sorting operations based on provided arguments and functions. But what engine does the vanilla sort, the one with no parameters, employ?

Taking a closer look at the WebKit source code (used by Chrome and Safari), we find that the algorithm choice depends on the type of array:

Numeric arrays or arrays containing primitive types: These arrays are sorted using the C std::qsort function, which typically implements a variation of quicksort (often introsort).

Contiguous arrays of non-numeric types: These arrays are converted to strings and sorted using mergesort (when possible for stability) or qsort (otherwise).

Other types (non-contiguous arrays and associative arrays): WebKit utilizes selection sort (min sort) or, in certain cases, sorts through an AVL tree for these types. Due to unclear documentation, tracing the code paths would be necessary to determine the specific algorithm used for each type.

Notably, the code contains a comment suggesting the use of a radix sort for faster sorting of stringified arrays, but this comment highlights a misunderstanding of radix sort's runtime complexity.

The above is the detailed content of What Sorting Algorithm Does JavaScript\'s `Array.sort()` Use?. For more information, please follow other related articles on the PHP Chinese website!