Sorting algorithms

Sorting puts elements in order. It looks simple, but different algorithms make very different trade-offs between speed, memory, stability and simplicity — which is why every course on algorithms starts here.

Comparison

Algorithm	Best	Average	Worst	Memory	Stable	In place
Bubble	n	n²	n²	1	yes	yes
Selection	n²	n²	n²	1	no	yes
Insertion	n	n²	n²	1	yes	yes
Shell	n log n	≈ n^1.25	n^1.5	1	no	yes
Merge	n	n log n	n log n	n	yes	no
Quick	n log n	n log n	n²	log n	no	yes
Heap	n log n	n log n	n log n	1	no	yes
Counting	n + k	n + k	n + k	n + k	yes	no
Radix	d(n + b)	d(n + b)	d(n + b)	n + b	yes	no

All complexities are O(…). k is the range of values, d the number of digits, b the base (10).

Key ideas

Comparison sorts (bubble … heap) only ask "is a less than b?". Any such algorithm needs at least ${\log }_{2}n!\approx n{\log }_{2}n$ comparisons in the worst case: there are $n!$ possible orders, and each comparison at best halves them. So O(n log n) is the best possible — merge sort and heap sort reach it always, quick sort on average.

Counting and radix sort are not comparison sorts: they use the values themselves as array indexes. That is how they beat n log n — but they only work for integers (or keys that can be turned into integers).

Stability — equal elements keep their original order. It matters when you sort records by one key after another: sort people by name, then stably by age, and people of the same age stay in alphabetical order.

In place — the algorithm needs only O(1) (or O(log n)) extra memory besides the array.

Which one to use

Situation	Choose
General purpose, fastest on average	Quick sort
Must be stable, or guaranteed n log n	Merge sort
Guaranteed n log n with O(1) memory	Heap sort
Small or almost sorted arrays	Insertion sort
Integers in a small range	Counting sort
Many integers with few digits	Radix sort
Learning the basics	Bubble, Selection

In production JavaScript Array.prototype.sort (TimSort, a hybrid of merge and insertion sort) is usually the right choice. This library shows how the classic algorithms work and gives you reliable implementations for courses, experiments and special cases.

Literature

• CLRS — T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to Algorithms, 4th ed., MIT Press, 2022. Chapters 2, 6, 7, 8.
• Sedgewick — R. Sedgewick, K. Wayne. Algorithms, 4th ed., Addison-Wesley, 2011. Chapter 2.
• Knuth — D. Knuth. The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed., 1998.