javascript - What is Array.prototype.sort() time complexity?

Question

According to Mozilla documentation :

The time and space complexity of the sort cannot be guaranteed as it depends on the implementation.

Is it at least safe to assume that it's not O(n^2)? Is there anywhere more detailed data about how it's implemented ? Thanks.

Answer 1

Firefox uses merge sort. Chrome, as of version 70, uses a hybrid of merge sort and insertion sort called Timsort.

The time complexity of merge sort is O(n log n). While the specification does not specify the sorting algorithm to use, in any serious environment, you can probably expect that sorting larger arrays does not take longer than O(n log n) (because if it did, it would be easy to change to a much faster algorithm like merge sort, or some other log-linear method).

While comparison sorts like merge sort have a lower bound of O(n log n) (i.e. they take at least this long to complete), Timsort takes advantages of "runs" of already ordered data and so has a lower bound of O(n).