Sorting, and which sort your language uses

The ground rules

A comparison sort learns about the data only by comparing pairs. There are n! possible orderings of n items, and each comparison at best halves the possibilities, so any comparison sort needs about log₂(n!) ≈ n log₂ n comparisons in the worst case. Merge sort, heapsort and Timsort reach that bound; quicksort reaches it on average.

Two properties matter as much as speed:

• Stability: items that compare equal stay in their original order. That lets you sort by a secondary key first and the primary key second, and it makes results predictable.
• Extra memory: merge-based sorts need a buffer of up to n/2 items; quicksort and heapsort sort in place.

Timsort: Python, Java objects, V8

Tim Peters wrote Timsort for Python in 2002. It scans the array for runs, stretches that are already ascending (or strictly descending, which it reverses), extends short runs to a minimum length with binary insertion sort, and merges runs pairwise using a stack of pending runs. When merging, it "gallops", jumping ahead exponentially when one run keeps winning. Real data is full of runs (appended logs, mostly sorted lists, concatenated sorted chunks), so Timsort often does far fewer than n log n comparisons:

On random data the count is close to n log₂ n (about 1.66 million for n = 100,000); on sorted data it is n − 1. Java's Arrays.sort for object arrays (and Collections.sort) is a Timsort adapted from Python's, V8 switched Array.prototype.sort to Timsort in V8 7.0 (Chrome 70), and since 3.11 CPython chooses which runs to merge with the "powersort" policy. ECMAScript has required sort to be stable since ES2019.

Introsort: C++ and .NET

Quicksort picks a pivot, partitions the array into smaller and larger items, and recurses into both sides. It is in place and very cache-friendly, which makes it fast on average, but bad pivots give O(n²). Introsort keeps quicksort's speed and removes that risk: it tracks recursion depth and switches to heapsort once the depth passes about 2 log₂ n, and it finishes small partitions (16 items or fewer in .NET) with insertion sort. .NET's Array.Sort documentation describes exactly this, and C++ implementations use it to meet the standard's O(n log n) requirement for std::sort. Neither is stable; C++ offers std::stable_sort when you need it.

Java uses a different trick for primitive arrays: Arrays.sort(int[]) is a dual-pivot quicksort. Stability means nothing for plain numbers, since two equal ints are indistinguishable.

What this means for you

Use the built-in sort, always with an explicit comparator for numbers in JavaScript. If you need a stable sort and your language doesn't promise one, add the original index as a tie-breaker. Sort once and keep the data sorted (insert with binary search, or use a sorted structure) rather than re-sorting on every request. If you only need the top k items, a heap is cheaper than a full sort.