Sorting Algorithm Interview Patterns
While most interviews don’t ask you to implement sorting from scratch, understanding the algorithms helps you choose the right sort for a given problem, explain time/space trade-offs, and solve custom comparison problems.
Quicksort
Average O(N log N), worst O(N^2) (sorted input with bad pivot). O(log N) space (call stack). In-place. Fastest in practice due to cache locality.
def quicksort(arr, lo, hi):
if lo >= hi: return
pivot = partition(arr, lo, hi)
quicksort(arr, lo, pivot - 1)
quicksort(arr, pivot + 1, hi)
def partition(arr, lo, hi):
pivot = arr[hi]
i = lo
for j in range(lo, hi):
if arr[j] <= pivot:
arr[i], arr[j] = arr[j], arr[i]; i += 1
arr[i], arr[hi] = arr[hi], arr[i]
return i
Randomized pivot: pick a random element as pivot to avoid O(N^2) worst case on sorted input. Python’s TimSort (hybrid merge + insertion) is used in production — never actually O(N^2) in practice.
Merge Sort
O(N log N) always. O(N) auxiliary space. Stable (preserves relative order of equal elements). Best for: external sort (data doesn’t fit in memory), stable sort requirements, linked lists (no random access needed).
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:]
Counting Sort / Radix Sort
Counting sort: O(N + K) where K = range of values. Only for integers in a known range. Use when N is large but K is small (e.g., sort 1M numbers all in range 0-1000).
Radix sort: O(N * d) where d = number of digits. Sort integers digit by digit using counting sort. O(N) for fixed-width integers. Use for very large N with bounded integer values.
Custom Sort — Comparator
import functools
# Sort by custom comparison:
# Largest number: concatenation order
def largest_number(nums):
def cmp(a, b):
return 1 if str(a)+str(b) < str(b)+str(a) else -1
nums.sort(key=functools.cmp_to_key(cmp))
return '0' if nums[0] == 0 else ''.join(map(str, nums))
Partial Sort — Top-K with Quickselect
def quickselect(arr, k):
"""Find kth smallest in O(N) average."""
lo, hi = 0, len(arr) - 1
while lo < hi:
pivot = partition(arr, lo, hi)
if pivot == k: break
elif pivot < k: lo = pivot + 1
else: hi = pivot - 1
return arr[k]
Dutch National Flag (3-way partition)
def sort_colors(nums):
lo, mid, hi = 0, 0, len(nums) - 1
while mid <= hi:
if nums[mid] == 0: nums[lo], nums[mid] = nums[mid], nums[lo]; lo += 1; mid += 1
elif nums[mid] == 1: mid += 1
else: nums[mid], nums[hi] = nums[hi], nums[mid]; hi -= 1
Interview Tips
- Stability matters when sorting objects by one key when they’re already sorted by another (e.g., sort by last name, then by first name stably).
- External sort: split file into M chunks that fit in RAM, sort each, K-way merge on disk.
- Custom comparator: use functools.cmp_to_key in Python to convert a comparator to a key function.
- Quickselect for Kth element: O(N) average, O(1) extra space — faster than heap O(N log K) when K ≈ N/2.
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “When does quicksort degrade to O(N^2) and how do you prevent it?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Quicksort degrades to O(N^2) when the partition is always maximally unbalanced — one side has 0 elements, the other has N-1. This happens when: (1) the array is already sorted and you always pick the first or last element as pivot, (2) all elements are equal (every partition is maximally unbalanced). Fix: random pivot selection — choose a random index as pivot before partitioning. With a random pivot, the expected performance is O(N log N) regardless of input order. Proof: the probability of consistently bad pivots is astronomically small. Alternative: median-of-three — pick the median of nums[lo], nums[mid], nums[hi] as the pivot. Eliminates sorted-input worst case without full randomization overhead. Python's timsort and Java's Arrays.sort use a combination of merge sort and insertion sort (timsort for objects) or dual-pivot quicksort (for primitives) — never O(N^2) in practice. For interview: state "random pivot to avoid worst case" and you've addressed the concern.” }
},
{
“@type”: “Question”,
“name”: “What sorting algorithm should you use for each scenario?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “General in-memory sort, primitives: Quicksort (average O(N log N), in-place, cache-friendly). Python uses timsort which is merge sort + insertion. General in-memory sort, stability required: Merge sort (O(N log N), O(N) space, stable). Stable = equal elements maintain original relative order. Needed when sorting objects by multiple keys. Small N (< 32): Insertion sort (O(N^2) worst case but O(N) for nearly sorted, very low constant). Timsort uses insertion sort for small runs. Integer values in range [0, K]: Counting sort (O(N+K), K is the value range). Use when K is small relative to N. Multi-digit integers or strings of fixed length: Radix sort (O(N*d) where d = digits). External sort (file too large for RAM): Merge sort variant — split into M chunks that fit in RAM, sort each, K-way merge on disk. For interview: know that Python's sorted() is timsort O(N log N) stable, and when counting sort applies (integers with small range). Being able to explain why stability matters (multi-key sorting) separates strong from average candidates.” }
},
{
“@type”: “Question”,
“name”: “How does the Dutch National Flag algorithm work?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Dutch National Flag (sort array with 3 distinct values, e.g., 0, 1, 2): three-way partitioning in O(N) time and O(1) space. Maintain three pointers: lo (boundary of 0s), mid (current), hi (boundary of 2s). Invariant: arr[0..lo-1] are all 0, arr[lo..mid-1] are all 1, arr[hi+1..n-1] are all 2, arr[mid..hi] are unexplored. Process: if arr[mid]==0: swap(lo, mid), lo++, mid++ (the 0 is placed, 1-region shrinks from left); if arr[mid]==1: mid++ (already in correct region); if arr[mid]==2: swap(mid, hi), hi– (the 2 is placed, but don't increment mid — the swapped element is unexplored). Stop when mid > hi. Time O(N), each element examined at most once. Practical application: sort colors (LeetCode 75), three-way quicksort (handles duplicate keys efficiently — partition into < pivot, == pivot, > pivot), and any problem with three categorical values. The key insight: mid advances only when the current element is finalized; the hi swap brings an unknown element to mid, so mid must not advance.” }
}
]
}