Why Sorting Matters in Interviews
Sorting is foundational: dozens of problems become O(n log n) after sorting (two-sum, 3-sum, interval merge, meeting rooms, closest pairs). Know the trade-offs: stability, in-place vs extra space, best/average/worst case. Interviewers often ask why you chose a specific sort or expect you to implement one.
Merge Sort
Divide the array in half recursively until single elements; merge sorted halves. Merge: two-pointer merge of two sorted arrays into a third. Time: O(n log n) guaranteed (all cases). Space: O(n) auxiliary. Stable. Use merge sort when: stability is required, you are sorting linked lists (no random access needed), external sorting (data does not fit in memory — merge sorted chunks from disk).
def merge_sort(arr):
if len(arr) <= 1: return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: result.append(left[i]); i += 1
else: result.append(right[j]); j += 1
return result + left[i:] + right[j:]Quick Sort
Choose a pivot; partition array into elements less than pivot, the pivot, and elements greater. Recurse on both halves. Time: O(n log n) average, O(n^2) worst (sorted array with naive pivot). Space: O(log n) stack (average). Not stable. In practice, faster than merge sort due to cache locality and low constant factor. Mitigate worst case: random pivot selection or median-of-three. Used in Python (Timsort uses merge sort + insertion sort), Java (dual-pivot quicksort for primitives).
Heap Sort
Build a max-heap from the array (O(n) via heapify). Repeatedly extract the max (O(log n)) and place at the end. Time: O(n log n) guaranteed. Space: O(1) in-place. Not stable. Less used in practice due to poor cache performance (non-sequential memory access). Good when guaranteed O(n log n) and O(1) space are both required.
Counting Sort and Radix Sort
Counting Sort: for integers in range [0, k]. Count occurrences, compute prefix sums, place elements. Time O(n+k), space O(k). Stable. Use when k is small (e.g., sorting by age, grade). Not comparison-based — bypasses the O(n log n) comparison lower bound.
Radix Sort: sort by each digit from least significant to most significant (LSD) using counting sort as the stable subroutine. Time O(d*(n+k)) where d = number of digits, k = base (10 for decimal). Used for sorting large integers or strings of fixed length. O(n) for fixed-size integers.
Timsort (Python / Java default)
Hybrid of merge sort and insertion sort. Identifies naturally occurring sorted runs in the input (many real-world arrays are partially sorted). Merges runs using a stack-based strategy. O(n) on already-sorted inputs, O(n log n) worst case. Stable. This is why Python sort and Java Arrays.sort(Object[]) are O(n) best case.
When to Use Which Sort
| Sort | Time | Space | Stable | Use When |
|---|---|---|---|---|
| Merge Sort | O(n log n) | O(n) | Yes | Stability needed, linked lists, external sort |
| Quick Sort | O(n log n) avg | O(log n) | No | General purpose, primitives |
| Heap Sort | O(n log n) | O(1) | No | Guaranteed O(n log n) + O(1) space |
| Counting Sort | O(n+k) | O(k) | Yes | Small integer range |
| Radix Sort | O(d*(n+k)) | O(n+k) | Yes | Fixed-length integers/strings |
Key Interview Points
- Sorting a list of objects by multiple keys: use Python key=(lambda x: (x.a, x.b)) — Timsort is stable so multi-pass sorting works
- Finding the kth largest element: QuickSelect — O(n) average, O(n^2) worst — or a min-heap of size k
- External sort: merge sort chunks that fit in memory; merge sorted files using a k-way merge with a min-heap
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “What is the time and space complexity of merge sort vs quicksort?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Merge sort: O(n log n) time in all cases (best, average, worst). O(n) space for the auxiliary merge buffer. Stable. Quicksort: O(n log n) average, O(n^2) worst case (sorted input with naive pivot). O(log n) stack space average (O(n) worst with bad pivot choices). Not stable. In practice, quicksort is 2-3x faster than merge sort on random data due to cache locality — sequential memory access during partitioning vs non-sequential during merge. Python uses Timsort (merge sort + insertion sort), O(n) on nearly sorted inputs. Java uses dual-pivot quicksort for primitives (average O(n log n) but with smaller constant) and Timsort for objects (stable).”
}
},
{
“@type”: “Question”,
“name”: “When should you use counting sort instead of a comparison sort?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Use counting sort when elements are non-negative integers in a small, known range [0, k]. Counting sort: count occurrences of each value, compute prefix sums, place elements in output array. O(n+k) time, O(k) space, stable. Beats O(n log n) comparison sorts when k = O(n). Examples: sort students by grade (0-100), sort characters in a string (k=26 or 256), sort ages (0-150), sort items by priority (1-5). Do NOT use when: k >> n (wastes space), elements are not integers, or elements span a large unknown range. Radix sort extends counting sort to multi-digit integers by sorting digit by digit, achieving O(d*n) where d is number of digits.”
}
},
{
“@type”: “Question”,
“name”: “How does the quickselect algorithm find the kth largest element in O(n)?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Quickselect is quicksort without fully sorting both halves. Partition the array around a pivot. If the pivot lands at index k (0-indexed from right), return it. If pivot index > k, recurse on the left half. If pivot index < k, recurse on the right half. Average O(n) because each partition eliminates about half the elements. Worst case O(n^2) with bad pivots — use random pivot to avoid. For guaranteed O(n) worst case, use the Median of Medians algorithm (more complex, rarely needed in interviews). Heap alternative: maintain a min-heap of size k. Push each element; when heap exceeds size k, pop the minimum. Final heap top is the kth largest. O(n log k) time, O(k) space."
}
},
{
"@type": "Question",
"name": "What is the difference between stable and unstable sorting?",
"acceptedAnswer": {
"@type": "Answer",
"text": "A stable sort preserves the relative order of elements with equal keys. An unstable sort may reorder equal elements. Example: sorting students by grade — stable sort keeps students with the same grade in their original order (e.g., alphabetical if previously sorted by name). Stable: merge sort, Timsort, counting sort, insertion sort. Unstable: quicksort, heap sort, selection sort. When stability matters: multi-key sorting (sort by date then by name — if the name sort is stable, records with the same name remain date-sorted). In Python, sort() is Timsort (stable), so you can chain sorts: sort by secondary key first, then primary key. In Java, Arrays.sort for primitives is unstable (dual-pivot quicksort); Arrays.sort for objects is stable (Timsort)."
}
},
{
"@type": "Question",
"name": "How do you implement an external sort for data larger than memory?",
"acceptedAnswer": {
"@type": "Answer",
"text": "External sort uses merge sort adapted for disk I/O. Phase 1 (run generation): read chunks of data that fit in memory, sort each chunk in memory (any in-memory sort), write sorted chunks (runs) to disk. With M bytes of memory and N bytes of data: creates N/M sorted runs. Phase 2 (merge): k-way merge of all sorted runs using a min-heap. Load the first element from each run into the heap. Extract the minimum, write to output, load the next element from that run's file. O(n log k) comparisons where k = number of runs. Minimize disk seeks by using large sequential reads/writes. This is how databases sort data for ORDER BY on large tables and how distributed systems like Hadoop implement MapReduce shuffle."
}
}
]
}
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: LinkedIn Interview Guide
Asked at: Coinbase Interview Guide