Sorting Algorithms

Introduction to Sorting

Sorting is one of the most fundamental operations in computer science. It involves arranging data in a particular order (ascending or descending). Many algorithms and data structures rely on sorted data for efficiency. Understanding different sorting algorithms and their trade-offs is crucial for choosing the right one for your use case.

This comprehensive chapter covers the 8 most popular and widely-used sorting algorithms, each with different characteristics, complexity trade-offs, and optimal use cases. From simple comparison-based sorts to advanced hybrid algorithms, you'll learn when and how to apply each algorithm effectively.

The algorithms are organized by their approach:

• Comparison-Based: Bubble Sort, Selection Sort, Insertion Sort, Quick Sort, Merge Sort, Heap Sort
• Non-Comparison-Based: Radix Sort
• Hybrid: Tim Sort

Any sort that works only by comparing pairs of elements needs at least Ω(n log n) comparisons in the worst case, there are n! possible orderings and each comparison yields one bit, so a decision tree needs depth log₂(n!) = Θ(n log n). Merge sort and heap sort meet this bound. Radix sort appears to beat it only because it does not compare elements at all; it inspects their representation instead, which is a different model.

Sorting Algorithms

Algorithm Comparison

Here's a comprehensive comparison of all 8 sorting algorithms to help you choose the right one for your use case.

Algorithm Selection Guide

For Small Datasets (< 50 elements):

• Use Insertion Sort - Simple and efficient

For General-Purpose Sorting:

• Use your language's built-in sort. It is almost certainly one of the hybrids below, and it will beat anything you write.
• Use Tim Sort when you need stability and your data has existing order
• Use Merge Sort when you need a guaranteed bound and a simple implementation
• Use Quick Sort for fast in-place sorting, but randomize the pivot, and be aware of the O(n²) worst case

When Stability is Required:

• Use Merge Sort - Stable and efficient
• Use Insertion Sort - For small arrays
• Use Tim Sort - Default in many languages

When In-Place Sorting is Required:

• Use Heap Sort - Guaranteed O(n log n) in-place
• Use Quick Sort - Fast average case

For Special Cases:

• Integers with limited range: Radix Sort
• Nearly sorted data: Insertion Sort or Tim Sort
• Educational purposes: Bubble Sort or Selection Sort

What Real Standard Libraries Actually Use

None of the eight algorithms in this chapter is what your programming language's standard library will run when you call its sort function. Every serious language ships a hybrid sort that combines two or three of these algorithms with tuning parameters informed by decades of benchmarking. Knowing what your language's sort actually does is worth understanding because it affects when and how you should write your own.

• Python's list.sort() / sorted(): Timsort until Python 3.10, powersort-scheduled Timsort in Python 3.11 and later. Stable, adaptive to natural runs, O(n log n) worst case, O(n) best case, insertion sort for runs shorter than a computed minimum run length (16–32).
• Java's Arrays.sort(Object[]): Timsort with Josh Bloch's modifications. For primitive arrays (int[], etc.), Java uses a dual-pivot quicksort by Vladimir Yaroslavskiy, which is faster than single-pivot quicksort on typical inputs and does not need to preserve stability (primitives are indistinguishable).
• C++'s std::sort: introsort, quicksort with median-of-three pivoting, cutting off to insertion sort for subarrays under 16 elements, falling back to heapsort if the recursion depth exceeds 2 log₂ n. Unstable but very fast; the fastest general-purpose sort in most benchmarks. For stability use std::stable_sort, which is typically a merge sort.
• Rust's sort_unstable: pdqsort (pattern-defeating quicksort) by Orson Peters. Introsort with branchless partitioning and pattern detection for common cases (already sorted, reverse sorted, few unique values). Faster than introsort on essentially every input class. The stable sort is Timsort.
• Go's sort.Sort: introsort variant (since Go 1.19, pdqsort). Unstable; use sort.SliceStable for a stable sort.
• JavaScript engines: V8 (Chrome, Node.js) uses Timsort since V8 v7.0 (2018). Previously V8 used a mix of insertion sort and quicksort. SpiderMonkey (Firefox) uses merge sort. The ECMAScript specification requires Array.prototype.sort to be stable as of ES2019.

The common thread: every one of these production sorts started as a "plain" O(n log n) sort (mergesort, quicksort, or Timsort) and grew a small ecosystem of optimisations around it, base-case insertion sort, pattern detection, heapsort fallback, branchless inner loops. This is the pattern: for the last two decades, no new "elementary" sort has beaten the hybrids on any workload that matters, but incremental refinements of the hybrids continue to produce measurable speedups.

Why Stability Matters More Than You Might Think

Sort stability, the property that equal elements preserve their input order, sounds like a niche concern, but it is critical for one common pattern: sorting a compound record by one field at a time, with each pass preserving the ordering established by the previous.

Suppose you have a list of employees and want them sorted by department, then by surname within department, then by first name within surname. The natural way to do this with a stable sort is:

1. Sort by first name (stable, so identical first names keep input order).
2. Sort the result by surname (stable, so within each surname the first names stay ordered from step 1).
3. Sort the result by department (stable, so within each department the surname+first-name ordering from step 2 is preserved).

This is called lexicographic sorting and it is the standard way to handle multi-key sorts in databases and spreadsheets. It works only because each sort is stable. With an unstable sort, you would need to construct explicit compound keys and compare them all at once, more code, more allocation, less flexibility.

This is the reason SQL's ORDER BY, Python's list.sort(), and JavaScript's Array.prototype.sort (as of ES2019) all guarantee stability. It is why C++'s std::sort and Rust's sort_unstable are named explicitly to signal that stability is not guaranteed, if you need it, you use std::stable_sort or slice::sort instead, and you pay a small performance cost for the guarantee.

What Standard Libraries Actually Use

None of the eight algorithms above is what runs when you call sort() in a modern language. Production sorts are hybrids that switch strategy based on the data, and it is worth knowing which one you are actually getting:

Two ideas recur across all of them. Switch to insertion sort on small subarrays (typically under 16–32 elements), where its low overhead and cache friendliness beat any asymptotically better algorithm. And bound the worst case: introsort falls back to heap sort when quicksort recursion runs too deep, while pdqsort detects bad patterns and breaks them up.

Sorts Not Covered Here

• Counting Sort: O(n + k) for integer keys in a small range k. Worth knowing in its own right, Radix Sort is built out of repeated counting sorts.
• Bucket Sort: distributes into buckets, sorts each, concatenates. O(n) on uniformly distributed data.
• Introsort / pdqsort: the hybrids described above.
• Shell Sort: insertion sort over diminishing gaps; simple, in-place, and better than O(n²) in practice.
• Cycle Sort: O(n²) comparisons but provably the minimum possible number of writes, which matters for flash memory or EEPROM where writes wear out the medium.
• External merge sort: for data too large for RAM, sort chunks that fit in memory, then k-way merge the sorted runs from disk.

What's Next?

Now that you understand sorting algorithms, explore related topics:

• Searching Algorithms - Binary search requires sorted data
• Recursion & Divide-and-Conquer - Used in merge sort and quick sort
• Trees - Heap sort uses binary heaps