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
1. Bubble Sort
A simple comparison-based sorting algorithm that repeatedly steps through the list and swaps adjacent elements if they are in the wrong order.
- Time Complexity: O(n²) worst/average, O(n) best
- Space Complexity: O(1)
- Best For: Educational purposes, small datasets
- Type: Comparison-Based
2. Quick Sort
A divide-and-conquer algorithm that picks a pivot element and partitions the array around the pivot, with excellent average-case performance.
- Time Complexity: O(n log n) average, O(n²) worst
- Space Complexity: O(log n)
- Best For: General-purpose sorting, large datasets
- Type: Comparison-Based
3. Selection Sort
A simple in-place comparison-based sorting algorithm that repeatedly finds the minimum element and places it at the beginning.
- Time Complexity: O(n²)
- Space Complexity: O(1)
- Best For: Small datasets, minimizing swaps
- Type: Comparison-Based
4. Insertion Sort
An efficient sorting algorithm for small datasets and nearly sorted arrays, building the sorted array one element at a time.
- Time Complexity: O(n²) worst/average, O(n) best
- Space Complexity: O(1)
- Best For: Small arrays, nearly sorted data
- Type: Comparison-Based
5. Merge Sort
A divide-and-conquer algorithm that divides the array into two halves, sorts them recursively, and merges the sorted halves.
- Time Complexity: O(n log n)
- Space Complexity: O(n)
- Best For: Stable sorting, guaranteed O(n log n)
- Type: Comparison-Based
6. Heap Sort
An in-place sorting algorithm that uses a binary heap data structure to sort elements, providing guaranteed O(n log n) performance.
- Time Complexity: O(n log n)
- Space Complexity: O(1)
- Best For: In-place sorting with guaranteed performance
- Type: Comparison-Based
7. Radix Sort
A non-comparison-based sorting algorithm that sorts numbers by processing individual digits, potentially achieving O(n) performance.
- Time Complexity: O(d × n) where d is number of digits
- Space Complexity: O(n + k)
- Best For: Integers, fixed-length keys
- Type: Non-Comparison-Based
8. Tim Sort
A hybrid stable sorting algorithm derived from merge sort and insertion sort, designed for real-world data with excellent performance.
- Time Complexity: O(n log n) worst, O(n) best
- Space Complexity: O(n)
- Best For: General-purpose, partially sorted data
- Type: Hybrid
Algorithm Comparison
Here's a comprehensive comparison of all 8 sorting algorithms to help you choose the right one for your use case.
| Algorithm | Best Case | Average Case | Worst Case | Space | Stable |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) avg, O(n) worst | No |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Radix Sort | O(d × n) | O(d × n) | O(d × n) | O(n + k) | Yes |
| Tim Sort | O(n) | O(n log n) | O(n log n) | O(n) | Yes |
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 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:
| Language / Library | Algorithm | Stable? |
|---|---|---|
Python sorted(), list.sort() |
Tim Sort (with powersort merge policy since 3.11) | Yes |
Java Arrays.sort(Object[]) |
Tim Sort | Yes |
Java Arrays.sort(int[]) |
Dual-pivot quicksort | No |
C++ std::sort |
Introsort (quicksort → heapsort → insertion sort) | No |
C++ std::stable_sort |
Merge sort (in-place variant if memory is tight) | Yes |
Rust sort_unstable, Go sort (1.19+) |
pdqsort (pattern-defeating quicksort) | No |
Rust sort |
Driftsort (Tim Sort-derived) | Yes |
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