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.
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”How do you count inversions in an array efficiently?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”An inversion is a pair (i, j) where i < j but arr[i] > arr[j]. Brute force O(n^2): check all pairs. Efficient O(n log n): modify merge sort. During the merge step, when a right-half element is placed before a left-half element, it forms an inversion with all remaining elements in the left half. Count += mid – left_pointer at that moment. This is exactly the merge sort algorithm with one extra counter increment. This technique counts all inversions in O(n log n) time and is the canonical solution to LC 315 (Count of Smaller Numbers After Self) when elements can repeat – use a BIT with coordinate compression for the exact count per element.”}},{“@type”:”Question”,”name”:”How does Quickselect find the kth largest element in O(n) average time?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Quickselect is Quicksort without recursing into both halves. Partition the array around a pivot (Lomuto or Hoare partition). After partitioning, the pivot is in its final sorted position. If pivot index == k-1 (for kth largest from largest): done. If pivot index > k-1: recurse into left half only. If pivot index < k-1: recurse into right half only. Average case: T(n) = T(n/2) + O(n) = O(n). Worst case: O(n^2) with bad pivot choice – use random pivot selection to make worst case rare. Never use Quickselect when a guaranteed O(n log n) bound is required – use a heap (O(n log k)) or merge sort instead. LC 215.”}},{“@type”:”Question”,”name”:”What is the Dutch National Flag problem and why is it important?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Sort an array with only 3 distinct values (e.g., 0, 1, 2) in O(n) time and O(1) space – one pass. Three pointers: low (boundary below which all elements < mid value), mid (current element), high (boundary above which all elements > mid value). While mid <= high: if arr[mid] == 0, swap with arr[low], increment both low and mid. If arr[mid] == 2, swap with arr[high], decrement high (do not increment mid – the swapped element is unexamined). If arr[mid] == 1, increment mid. This is LC 75 (Sort Colors). The same 3-way partition is used in Quicksort for arrays with many duplicate keys (eliminates the O(n^2) worst case on arrays like [1,1,1,1,1]).”}},{“@type”:”Question”,”name”:”How does cyclic sort work for finding missing or duplicate numbers?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”For an array containing n values in range [1, n] (possibly with duplicates or missing values): place each element at its correct index (arr[i] should equal i+1). Iterate: if arr[i] != i+1 and arr[arr[i]-1] != arr[i], swap arr[i] with arr[arr[i]-1]. Otherwise, move to i+1. After one pass, any index i where arr[i] != i+1 indicates either a missing value (i+1 is missing) or a duplicate (arr[i] is the duplicate). O(n) time, O(1) space. Applications: LC 268 (Missing Number), LC 287 (Find Duplicate), LC 448 (Find All Disappeared Numbers), LC 442 (Find All Duplicates). Avoids sorting or using a hash set.”}},{“@type”:”Question”,”name”:”How do you sort strings to form the largest number (LC 179)?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Intuition: to decide if string a should come before b, compare which concatenation is larger: a+b vs b+a. If a+b > b+a, a comes first. This comparison defines a total ordering. Implement as a custom comparator: compare(a, b) = 1 if a+b > b+a else -1. Sort with this comparator. Edge case: if all strings are "0", return "0" (not "0000"). In Python, use functools.cmp_to_key to convert a comparison function to a key function for sorted(). The key insight is that the concatenation order comparison is transitive and defines a valid total order, making the sort correct. O(n * L * log n) where L is average string length.”}}]}
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.