Sorting problems appear constantly in interviews – not just “implement merge sort” but as tools to simplify harder problems. Master these patterns and you will recognize when sorting is the key insight.
Merge Sort
Merge sort is the go-to stable, O(n log n) sort. Divide into halves, sort each, merge back. The merge step is where the real work happens.
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
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
result.extend(left[i:])
result.extend(right[j:])
return result
Bonus application – count inversions: An inversion is a pair (i, j) where i < j but arr[i] > arr[j]. Modify the merge step: every time you pick from the right array, all remaining left elements form inversions with it.
def merge_count(arr):
if len(arr) <= 1:
return arr, 0
mid = len(arr) // 2
left, lc = merge_count(arr[:mid])
right, rc = merge_count(arr[mid:])
merged, mc = merge_and_count(left, right)
return merged, lc + rc + mc
def merge_and_count(left, right):
result = []
inversions = 0
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
# All remaining left[i:] are greater than right[j]
inversions += len(left) - i
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result, inversions
Quick Sort and Quickselect
Quick sort partitions around a pivot so everything left is smaller, everything right is larger, then recurses. Average O(n log n), worst O(n^2) with bad pivot choice.
# Lomuto partition scheme
def quicksort(arr, lo, hi):
if lo < hi:
pivot_idx = partition(arr, lo, hi)
quicksort(arr, lo, pivot_idx - 1)
quicksort(arr, pivot_idx + 1, hi)
def partition(arr, lo, hi):
pivot = arr[hi]
i = lo - 1
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[hi] = arr[hi], arr[i + 1]
return i + 1
Quickselect finds the kth smallest element in O(n) average. After partitioning, only recurse into the side containing k – no need to sort both halves. This solves LC 215 (kth largest element) without sorting the whole array.
def quickselect(arr, k):
# Returns kth smallest (0-indexed)
def select(lo, hi):
if lo == hi:
return arr[lo]
pivot_idx = partition(arr, lo, hi)
if k == pivot_idx:
return arr[pivot_idx]
elif k < pivot_idx:
return select(lo, pivot_idx - 1)
else:
return select(pivot_idx + 1, hi)
return select(0, len(arr) - 1)
# LC 215: kth largest - find (n-k)th smallest
def findKthLargest(nums, k):
n = len(nums)
target = n - k
def select(lo, hi):
pivot_idx = partition(nums, lo, hi)
if pivot_idx == target:
return nums[pivot_idx]
elif pivot_idx < target:
return select(pivot_idx + 1, hi)
else:
return select(lo, pivot_idx - 1)
return select(0, n - 1)
Hoare partition is faster in practice (fewer swaps) but trickier to implement. Use Lomuto in interviews unless asked specifically.
Counting Sort and Radix Sort
When the value range is small and known, counting sort runs in O(n + k) where k is the range – breaking the O(n log n) comparison sort lower bound.
def counting_sort(arr, max_val):
counts = [0] * (max_val + 1)
for x in arr:
counts[x] += 1
result = []
for val, cnt in enumerate(counts):
result.extend([val] * cnt)
return result
# Stable counting sort (preserves relative order - needed for radix sort)
def counting_sort_stable(arr, max_val):
counts = [0] * (max_val + 1)
for x in arr:
counts[x] += 1
# Prefix sums give start positions
for i in range(1, len(counts)):
counts[i] += counts[i - 1]
result = [0] * len(arr)
for x in reversed(arr):
counts[x] -= 1
result[counts[x]] = x
return result
Use counting sort when: values are non-negative integers, range is O(n) or smaller, you need O(n) time. Classic use cases: sort characters in a string, sort ages, sort scores 0-100.
Sorting as Preprocessing
Many problems that look hard become straightforward after sorting. This is often the intended insight.
# Merge Intervals (LC 56) - sort by start, then greedy merge
def merge_intervals(intervals):
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for start, end in intervals[1:]:
if start <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
return merged
# Meeting Rooms II (LC 253) - sort start/end separately
def min_meeting_rooms(intervals):
starts = sorted(x[0] for x in intervals)
ends = sorted(x[1] for x in intervals)
rooms = 0
max_rooms = 0
j = 0
for i in range(len(starts)):
if starts[i] < ends[j]:
rooms += 1
max_rooms = max(max_rooms, rooms)
else:
rooms -= 1
j += 1
return max_rooms
# Two Sum variant - sorted array, two pointers O(n)
def two_sum_sorted(arr, target):
lo, hi = 0, len(arr) - 1
while lo < hi:
s = arr[lo] + arr[hi]
if s == target:
return [lo, hi]
elif s < target:
lo += 1
else:
hi -= 1
return []
Other classic preprocessing sorts: closest pair of points (sort by x, use sweep), k closest points to origin (sort by distance), minimum number of arrows to burst balloons (sort by end).
Custom Comparator Patterns
Python’s sort is stable and uses a key function. For complex comparisons, use functools.cmp_to_key.
import functools
# Sort by length then lexicographically
words = ["banana", "apple", "fig", "date"]
words.sort(key=lambda w: (len(w), w))
# Sort intervals by end time (greedy interval scheduling)
intervals.sort(key=lambda x: x[1])
# LC 179: Largest Number - custom comparator
# Compare "ab" vs "ba" by checking which concatenation is larger
def largest_number(nums):
strs = list(map(str, nums))
def compare(a, b):
if a + b > b + a:
return -1 # a should come first
elif a + b < b + a:
return 1
return 0
strs.sort(key=functools.cmp_to_key(compare))
result = ''.join(strs)
return '0' if result[0] == '0' else result
# Sort tasks by frequency descending, then by character for tie-breaking
from collections import Counter
tasks = "AABBC"
freq = Counter(tasks)
sorted_tasks = sorted(freq.keys(), key=lambda c: (-freq[c], c))
Dutch National Flag / 3-Way Partition
LC 75 (Sort Colors): partition array into three groups (0s, 1s, 2s) in one pass O(n) time O(1) space. Three pointers: low (next 0 position), mid (current), high (next 2 position).
def sortColors(nums):
low = 0
mid = 0
high = len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1
mid += 1
elif nums[mid] == 1:
mid += 1
else: # nums[mid] == 2
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1
# Don't increment mid - need to check swapped element
Generalizes to any 3-way partition problem. Key insight: when you swap from high, you don’t advance mid because the swapped element is unknown. When you swap from low, both low and mid advance because low only contains 0s at that point.
Cyclic Sort
For arrays where values are in range [1..n] or [0..n-1], cyclic sort places each element at its correct index in O(n) time O(1) space. After sorting, any mismatch reveals missing or duplicate values.
def cyclic_sort(nums):
i = 0
while i < len(nums):
correct_idx = nums[i] - 1 # value 1 belongs at index 0
if nums[i] != nums[correct_idx]:
nums[i], nums[correct_idx] = nums[correct_idx], nums[i]
else:
i += 1
return nums
# Find missing number (LC 268) - after cyclic sort, find where arr[i] != i+1
def find_missing(nums):
cyclic_sort(nums)
for i in range(len(nums)):
if nums[i] != i + 1:
return i + 1
return len(nums)
# Find all duplicates (LC 442)
def find_duplicates(nums):
cyclic_sort(nums)
result = []
for i in range(len(nums)):
if nums[i] != i + 1:
result.append(nums[i])
return result
Sort Decision Guide
- Need stable sort, guaranteed O(n log n): Merge sort. Also use when counting inversions.
- In-place sort, average O(n log n): Quick sort. Use randomized pivot to avoid O(n^2) worst case.
- Find kth element, O(n) average: Quickselect.
- Values in known small range [0..k]: Counting sort O(n + k).
- Integers, sort digit by digit: Radix sort O(d * n).
- Partition into 3 groups in one pass: Dutch national flag.
- Array values 1..n, find missing/duplicate: Cyclic sort.
- Custom ordering logic: Python sort with key or cmp_to_key.
- Problem with intervals, pairs, or “closest” queries: Try sorting as preprocessing first.
Meta coding interviews test sorting algorithms and custom comparators. See common patterns for Meta interview: sorting and order statistics problems.
Databricks interviews cover sorting and distributed data processing. See patterns for Databricks interview: sorting and data processing patterns.
Apple coding rounds test sorting algorithm implementation. See patterns for Apple interview: sorting algorithm implementation.