Three sorts that matter, and why

All the O(n log n) sorts have the same complexity and behave differently. The differences are what gets asked about.

Merge sort

Split in half, sort each half, merge the two sorted halves.

[38, 27, 43, 3]
[38, 27] [43, 3]
[27, 38] [3, 43]
[3, 27, 38, 43]

Always O(n log n), because the split is always even regardless of the data. Needs O(n) extra space to merge into. It is stable, meaning equal elements keep their original order.

Quicksort

Pick a pivot, move smaller elements left and larger right, recurse on each side.

Average O(n log n) and worst case O(n squared), which happens when the pivot is consistently the smallest or largest. On an already sorted array with a first element pivot, that is exactly what happens, which is why real implementations pick the pivot randomly or by median of three.

Usually the fastest in practice despite the worse worst case, because it sorts in place and its memory access pattern is friendly to the cache.

Heapsort

Build a heap, then repeatedly extract the minimum.

O(n log n) always, and O(1) extra space. Both guarantees at once, which neither of the others gives. It is slower than quicksort in practice because it jumps around memory, and it is not stable.

Why stability matters

Sort employees by name, then by department. If the second sort is stable, people stay alphabetical within each department. If not, that ordering is lost and the result looks arbitrary.

This is why sorted() in Python and Collections.sort in Java are stable and guarantee it, while C++ std::sort does not and std::stable_sort exists separately.

What the standard library actually does

Most are hybrids. Timsort, in Python and Java for objects, finds runs that are already ordered and merges them, so nearly sorted input approaches O(n). Introsort, in C++, runs quicksort and switches to heapsort when the recursion gets too deep, which caps the worst case at O(n log n).

Insertion sort survives inside all of them: it is O(n squared) and genuinely fastest below about 16 elements, so the recursion stops early and finishes with it.

The O(n) sorts

Counting sort and radix sort beat n log n by not comparing elements. They need the keys to be small integers or fixed width, so they are not general, and where they apply they are very fast.