Why This Matters
Sorting is the most studied problem in computer science. Not because sorting itself is glamorous, but because it appears everywhere: binary search needs sorted input, database indexes maintain sort order, and scheduling algorithms prioritize by sorted criteria. Interview questions about sorting test whether you understand trade-offs, not whether you can recite code.
Sorting Properties
Before comparing algorithms, you need the vocabulary interviewers use.
Stable -- a sort is stable if equal elements keep their original relative order. If you sort students by grade and two students both have a B, a stable sort preserves whoever appeared first in the original list. Merge sort and insertion sort are stable. Quick sort and heap sort are not.
In-place -- a sort is in-place if it uses O(1) extra memory (ignoring the input array and call stack). Selection sort and insertion sort are in-place. Merge sort is not -- it needs O(n) auxiliary space for merging.
Adaptive -- a sort is adaptive if it runs faster on partially sorted input. Insertion sort is adaptive: O(n) on nearly-sorted data. Selection sort is not: it always does the same number of comparisons regardless of input order.
The Comparison-Based Lower Bound
Any sorting algorithm that works by comparing elements has a worst-case lower bound of O(n log n). The proof uses a decision tree argument: n! possible permutations require at least log2(n!) comparisons to distinguish, and log2(n!) = Theta(n log n).
This means bubble sort, selection sort, and insertion sort (all O(n^2) worst case) are provably suboptimal for large inputs. Merge sort, quick sort, and heap sort hit the O(n log n) floor.
Non-comparison sorts like counting sort and radix sort bypass this bound by exploiting the structure of the input (e.g., integers in a known range), but they are not general-purpose.
Bubble Sort
Repeatedly swaps adjacent out-of-order elements. Each pass "bubbles" the largest unsorted element to its final position.
- Time: O(n^2) average and worst. O(n) best with early-exit optimization (stop if a pass makes no swaps).
- Space: O(1). In-place.
- Stable: Yes.
- Adaptive: Yes, with early-exit flag.
Bubble sort's only real-world use is teaching. It does more swaps than insertion sort and has no advantage over it. If someone asks "which simple sort is strictly worse than the others in practice," the answer is bubble sort.
Selection Sort
Finds the minimum unsorted element and swaps it into position. Repeats until sorted.
- Time: O(n^2) always. No best-case shortcut -- it does n(n-1)/2 comparisons regardless of input order.
- Space: O(1). In-place.
- Stable: No (the swap can move equal elements out of order).
- Adaptive: No.
Selection sort's one advantage: it does at most n swaps. On hardware where writes are expensive (e.g., flash memory), minimizing swaps matters. Otherwise, insertion sort is preferred.
Insertion Sort
Builds the sorted array one element at a time. Takes each element and shifts larger elements right to make room.
- Time: O(n^2) worst (reverse-sorted input). O(n) best (already sorted -- each element requires zero shifts).
- Space: O(1). In-place.
- Stable: Yes.
- Adaptive: Yes -- performance scales with how far each element is from its sorted position.
Insertion sort is the most practical of the three elementary sorts. Real-world sorting libraries (Python's Timsort, Go's sort package) switch to insertion sort for small subarrays (typically below 12-32 elements) because its low overhead beats the constant factors of more complex algorithms at small n.
Real-World Hybrid Sorts
No production sorting library uses a single algorithm. The two most common hybrids:
Timsort (Python, Java for objects) -- merge sort + insertion sort. Finds naturally ordered runs in the data, extends short runs with insertion sort, then merges runs. Exploits real-world data that tends to have existing order.
Introsort (C++ STL, Go) -- quick sort + heap sort + insertion sort. Starts with quicksort, switches to heap sort if recursion depth exceeds 2*log(n) (to guarantee O(n log n) worst case), and finishes small partitions with insertion sort.
Key Takeaways
- Stable sorts preserve the relative order of equal elements. Merge sort and insertion sort are stable.
- The comparison-based sorting lower bound is O(n log n). Elementary O(n^2) sorts cannot beat this for large inputs.
- Insertion sort is the best elementary sort in practice -- adaptive, stable, and used as a building block inside Timsort and introsort.
- Selection sort minimizes swaps (at most n). Bubble sort has no practical advantage.