Sorting Algorithms
Sorting algorithms reorder a collection of elements according to a defined comparison criterion. They are among the most studied algorithms in computer science because sorting is a prerequisite for many other operations — binary search requires a sorted array, efficient set operations rely on sorted input, and database indexes are fundamentally sort structures. The right choice of sorting algorithm depends on input size, data distribution, memory constraints, and whether stability is required.
Sorting algorithms divide into two categories: comparison-based algorithms (bubble sort, merge sort, quicksort, heapsort), which are bounded below by O(n log n) by information-theoretic argument, and non-comparison algorithms (counting sort, radix sort, bucket sort), which can achieve O(n) by exploiting structural properties of the keys rather than comparing them.
Key Concepts
Stability — A stable sort preserves the relative order of equal elements. Merge sort is stable; standard quicksort and heapsort are not. Stability matters when sorting by multiple keys sequentially (e.g., sort by name, then by department).
In-place vs. Out-of-place — In-place sorts (quicksort, heapsort) use O(1) auxiliary space. Out-of-place sorts (merge sort) require O(n) extra memory but are easier to implement stably and work on linked structures.
Comparison of Common Algorithms:
| Algorithm | Time (avg) | Time (worst) | Space | Stable |
|---|---|---|---|---|
| Bubble sort | O(n²) | O(n²) | O(1) | Yes |
| Merge sort | O(n log n) | O(n log n) | O(n) | Yes |
| Quicksort | O(n log n) | O(n²) | O(log n) | No |
| Heapsort | O(n log n) | O(n log n) | O(1) | No |
| Counting sort | O(n + k) | O(n + k) | O(k) | Yes |
| Timsort | O(n log n) | O(n log n) | O(n) | Yes |
Timsort — Python’s sorted() and Java’s Arrays.sort() use Timsort, a hybrid of merge sort and insertion sort that exploits naturally ordered runs in real-world data, achieving near-O(n) on partially sorted input.
Quicksort Pivoting — Naive quicksort with the first element as pivot degrades to O(n²) on already-sorted input. Median-of-three pivot selection or randomized pivot selection reduces this risk significantly.
Common Pitfalls
- Using O(n²) sorts (bubble, insertion) on large datasets — fine for n < 50, catastrophic for n > 10,000
- Ignoring stability requirements when sorting objects with multiple meaningful fields
- Assuming library sort is always optimal — counting sort beats merge sort when k (key range) is small
Best Practices
- Default to your language’s built-in sort (usually Timsort or introsort) — it is well-tested and adaptive
- Use counting/radix sort when keys are bounded integers and n is large
- Test sort correctness with empty arrays, single-element arrays, and already-sorted inputs
Related Topics
- big-o-notation — Framework for analyzing and comparing algorithm time complexity
- searching-algorithms — Binary search requires sorted input; sorting and searching are complementary
- divide-and-conquer — Merge sort and quicksort are canonical divide-and-conquer algorithms