Why Sorting Matters for Interviews
Sorting appears in more interview problems than any other single topic. Sometimes you implement a sort from scratch; more often, sorting is a preprocessing step that turns an O(n²) brute-force into an O(n log n) elegant solution.
- Divide and conquer: Merge sort and quick sort teach you recursion at scale.
- Trade-off analysis: Time vs space, stability vs speed, in-place vs not — interviewers want you to reason about constraints.
- Preprocessing: Many problems (two-sum variants, duplicates, intervals) become trivial after sorting.
- Built-in knowledge: Knowing that Python's
sorted()uses TimSort (O(n log n), stable) lets you use it confidently and explain why.
Bubble Sort
Bubble sort repeatedly walks through the list, compares adjacent elements, and swaps them if they're in the wrong order. After each pass, the largest unsorted element "bubbles up" to its correct position. It's the simplest sort but also the slowest.
The swapped flag is the only optimization worth knowing: if no swaps happen during a pass, the list is already sorted. This gives bubble sort an O(n) best case on nearly-sorted data.
Selection Sort
Selection sort divides the array into a sorted and unsorted region. On each pass, it finds the minimum element in the unsorted region and swaps it into the sorted region. It always makes O(n²) comparisons, even on sorted data.
[(4,'a'), (3,'b'), (4,'c')] by first element — the swap of (4,'a') past (3,'b') can reorder equal 4s.
Insertion Sort
Insertion sort builds the sorted array one element at a time. It picks each element and inserts it into its correct position among the already-sorted elements — just like sorting a hand of playing cards.
Merge Sort — Visual Walkthrough
Merge sort is a divide-and-conquer algorithm. It splits the array in half recursively until each piece has one element, then merges the pieces back in sorted order. The key insight: merging two sorted arrays takes O(n) time.
Merge Sort on [38, 27, 43, 3, 9, 82, 10]
Merge Sort
Merge sort guarantees O(n log n) time in all cases — best, average, and worst. The trade-off is O(n) extra space for the temporary arrays during merging. It's stable and the go-to sort when stability matters and memory isn't constrained.
Complexity breakdown
- Split: log n levels of recursion (halving each time).
- Merge: Each level does O(n) work total (every element is compared once per level).
- Total: O(n) work * O(log n) levels = O(n log n).
- Space: O(n) for the temporary arrays at each merge step.
<= in if left[i] <= right[j] is what makes merge sort stable. If two elements are equal, the one from the left half (which came first in the original array) is placed first in the result.
Quick Sort — Partition Walkthrough
Quick sort picks a pivot, partitions the array so all elements smaller than the pivot go left and all larger go right, then recursively sorts both sides. The partition step is where the magic happens.
Partitioning [38, 27, 43, 3, 9, 82, 10] with pivot = 10
Quick Sort
Quick sort is the fastest general-purpose sort in practice. Its average case is O(n log n) with excellent constant factors and cache performance. The worst case O(n²) happens only with bad pivot choices (already-sorted data with first/last pivot).
In-place quick sort (interview version)
Counting Sort
Counting sort is a non-comparison sort. Instead of comparing elements, it counts how many times each value appears, then reconstructs the sorted array. It runs in O(n + k) time where k is the range of values — faster than O(n log n) when k is small.
Comparison Table
Here's every algorithm side by side. Memorize this table — interviewers love asking "which sort would you use and why?"
| Algorithm | Best | Average | Worst | Space | Stable? | In-place? |
|---|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No | Yes |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No | Yes |
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | O(n + k) | Yes | No |
Python's Built-in: sorted() and TimSort
In real interviews and production code, you'll use sorted() or .sort(). But you should know what's under the hood — interviewers ask.
- Invented by: Tim Peters, for Python in 2002. Now also used by Java, Android, V8 (JavaScript), Swift, and Rust.
- Hybrid of: Merge sort + insertion sort. It divides data into "runs" (naturally sorted subsequences), extends short runs using insertion sort, then merges runs using merge sort.
- Time: O(n log n) worst case, O(n) best case on nearly-sorted data.
- Space: O(n) for the temporary merge buffer.
- Stable: Yes — equal elements keep their original order.
sorted() returns a new list and works on any iterable (strings, tuples, generators). .sort() sorts a list in-place and returns None. A common bug: x = mylist.sort() — now x is None!
Try It Yourself
Implement Merge Sort
Complete the merge_sort() and merge() functions. Split the array in half recursively, then merge two sorted halves back together. Test with the provided array.
Challenge
Given an array nums with values 0, 1, and 2 (representing red, white, blue), sort them in-place so all 0s come first, then 1s, then 2s. Do it in one pass with O(1) space — no sorted() allowed.
Example: [2, 0, 2, 1, 1, 0] becomes [0, 0, 1, 1, 2, 2]
low, mid, high. When nums[mid] == 0, swap with low and advance both. When nums[mid] == 2, swap with high and decrement high (don't advance mid — the swapped value hasn't been checked). When nums[mid] == 1, just advance mid.Given a list of intervals [[1,3],[2,6],[8,10],[15,18]], merge all overlapping intervals. Return [[1,6],[8,10],[15,18]].
Approach: Sort by start time, then iterate and merge overlapping intervals.
interval[0]. Initialize merged = [intervals[0]]. For each remaining interval, if it overlaps with the last merged interval (interval[0] <= merged[-1][1]), extend: merged[-1][1] = max(merged[-1][1], interval[1]). Otherwise, append it as a new interval. Sorting takes O(n log n) and the merge pass takes O(n).Quiz
sorted() use internally?Common Mistakes
- Using
x = mylist.sort(). The.sort()method returnsNoneand sorts in-place. Usex = sorted(mylist)if you need a new list. - Forgetting quick sort's worst case. If you tell an interviewer "quick sort is always O(n log n)" — that's wrong. It's O(n²) worst case. Say "O(n log n) average, O(n²) worst case with bad pivot selection."
- Confusing stable vs unstable. Stability means equal elements keep their original relative order. Selection sort and quick sort (standard) are NOT stable. If the interviewer asks to sort by multiple keys, you need a stable sort.
- Using counting sort on huge ranges. Counting sort on values 1 to 10 billion allocates a 10-billion-element array. It's O(n + k) — if k is massive, stick with comparison sorts.
- Off-by-one in merge sort's merge step. Forgetting
result.extend(left[i:])after the while loop exits. One half is always exhausted first — the remaining elements in the other half still need to be appended.
Key Takeaways
- O(n²) sorts (bubble, selection, insertion) are simple to implement but too slow for large datasets. Insertion sort is useful for small or nearly-sorted data — Python's TimSort uses it internally.
- Merge sort guarantees O(n log n) always, is stable, but uses O(n) extra space. Use it when you need guaranteed performance and stability.
- Quick sort is fastest in practice (great cache performance, small constants) with O(n log n) average, but O(n²) worst case. Use random pivot or median-of-three to avoid the worst case.
- Counting sort runs in O(n + k) — faster than comparison sorts when the range of values is small. It's a non-comparison sort and doesn't hit the O(n log n) lower bound.
- Python's sorted() uses TimSort — a hybrid of merge sort and insertion sort. It's O(n log n) worst case, O(n) best case, stable, and the right choice for 99% of real-world Python code.
You've mastered 6 sorting algorithms.
Now sort your career into the right position.
Join the Best AI Programs — three 5-month courses, fully online, with placement assistance. Week 1 is free.
Explore our AI-era courses →