must-know junior · part of Skills & Topics · Senior SWE Roadmap · related: Arrays & Strings · Complexity Analysis · Heaps & Priority Queues · Two Pointers & Sliding Window
Why this matters / recognition signals
Sorting and binary search are the two most-reused primitives in the entire DSA toolkit — half of “clever” solutions are really just “sort first, then the real problem becomes easy” or “binary search on something that isn’t an array at all.” An interviewer expects you to implement both from memory, correctly, on the first try.
Recognition signals:
- “sort the array” as a sub-step before a two-pointer, greedy, or interval problem → the sort itself is rarely the hard part, but getting the comparator right is
- “find the target in a sorted array/rotated sorted array” → binary search
- “kth largest/smallest element” → heap (see Heaps & Priority Queues) or quickselect (a quicksort partition, stopped early)
- “minimum/maximum X such that some condition holds”, “smallest value that still works”, “find the boundary where the answer flips from no to yes” → binary search on the answer, even when nothing in the problem looks like a sorted array
- custom sort order (sort by frequency, sort strings by a derived key, stable multi-key sort) → comparator design, and whether stability matters
Core mechanism: merge sort (divide & conquer)
Split the array in half recursively until each piece has one element (trivially sorted), then merge sorted halves back together. The merge step is the only real work: walk two sorted subarrays with two pointers, always taking the smaller front element.
flowchart TD A["[5,3,8,1,9,2]"] --> B["[5,3,8]"] A --> C["[1,9,2]"] B --> D["[5,3]"] B --> E["[8]"] C --> F["[1,9]"] C --> G["[2]"] D --> H["[5]"] D --> I["[3]"] F --> J["[1]"] F --> K["[9]"] H --> M1["merge → [3,5]"] I --> M1 J --> M2["merge → [1,9]"] K --> M2 M1 --> M3["merge → [3,5,8]"] E --> M3 M2 --> M4["merge → [1,2,9]"] G --> M4 M3 --> Final["merge → [1,2,3,5,8,9]"] M4 --> Final
The recurrence is T(n) = 2T(n/2) + O(n) — two half-size subproblems plus O(n) work to merge them back together. That recurrence solves to O(n log n): there are log n levels of splitting, and each level does O(n) total merge work across all its subproblems.
Core mechanism: quicksort (partition-based)
Pick a pivot, partition the array so everything ≤ pivot ends up to its left and everything > pivot ends up to its right, then recurse on the two sides. Unlike merge sort, the partition step does the reordering in place — no auxiliary array — and the pivot itself ends up in its final sorted position after one partition pass.
flowchart LR subgraph Arr["[5,3,8,1,9,2] pivot = 2 (last element)"] direction LR A0["5"] --- A1["3"] --- A2["8"] --- A3["1"] --- A4["9"] --- A5["2"] end I["i: boundary of the '≤ pivot' region"] -.-> A0 J["j: scans left → right"] -.-> A0 Note["whenever arr[j] ≤ pivot: i++, swap(arr[i], arr[j]) after the scan: swap(arr[i+1], pivot) drops the pivot into its final sorted slot"]
This is the Lomuto partition scheme: i tracks the last index known to belong in the “small” region, j scans ahead looking for more small elements to fold in.
Worked numeric example
Quicksort partition trace
Array [5, 3, 8, 1, 9, 2], pivot = last element = 2. Starting i = -1.
| j | arr[j] | ≤ pivot (2)? | i after | array state | action |
|---|---|---|---|---|---|
| 0 | 5 | no | -1 | [5,3,8,1,9,2] | no swap |
| 1 | 3 | no | -1 | [5,3,8,1,9,2] | no swap |
| 2 | 8 | no | -1 | [5,3,8,1,9,2] | no swap |
| 3 | 1 | yes | 0 | [1,3,8,5,9,2] | swap(arr[0], arr[3]) |
| 4 | 9 | no | 0 | [1,3,8,5,9,2] | no swap |
| — | (pivot) | — | — | [1,2,8,5,9,3] | swap(arr[1], arr[5]) — pivot lands at index 1 |
After one partition pass: [1] | 2 | [8,5,9,3] — everything left of index 1 is ≤ 2, everything right is > 2, and index 1 (the pivot) is already in its final sorted position. Recurse independently on [1] and [8,5,9,3].
Binary search trace
Sorted array [1, 3, 5, 7, 9, 11, 13], target = 9.
| step | low | high | mid | arr[mid] | comparison | action |
|---|---|---|---|---|---|---|
| 1 | 0 | 6 | 3 | 7 | 7 < 9 | low = mid + 1 = 4 |
| 2 | 4 | 6 | 5 | 11 | 11 > 9 | high = mid - 1 = 4 |
| 3 | 4 | 4 | 4 | 9 | match | found at index 4 |
Java implementation
import java.util.Arrays;
public final class SortingAndSearching {
private SortingAndSearching() {}
// ---- Merge sort: O(n log n) time, O(n) space, stable ----
public static void mergeSort(int[] arr) {
if (arr.length < 2) return;
int[] buffer = new int[arr.length];
mergeSort(arr, buffer, 0, arr.length - 1);
}
private static void mergeSort(int[] arr, int[] buffer, int lo, int hi) {
if (lo >= hi) return;
int mid = lo + (hi - lo) / 2;
mergeSort(arr, buffer, lo, mid);
mergeSort(arr, buffer, mid + 1, hi);
merge(arr, buffer, lo, mid, hi);
}
private static void merge(int[] arr, int[] buffer, int lo, int mid, int hi) {
System.arraycopy(arr, lo, buffer, lo, hi - lo + 1);
int i = lo, j = mid + 1, k = lo;
while (i <= mid && j <= hi) {
arr[k++] = (buffer[i] <= buffer[j]) ? buffer[i++] : buffer[j++];
}
while (i <= mid) arr[k++] = buffer[i++];
while (j <= hi) arr[k++] = buffer[j++];
}
// ---- Quicksort: O(n log n) average, O(n^2) worst, in-place, NOT stable ----
public static void quickSort(int[] arr) {
quickSort(arr, 0, arr.length - 1);
}
private static void quickSort(int[] arr, int lo, int hi) {
if (lo >= hi) return;
int pivotIndex = partition(arr, lo, hi);
quickSort(arr, lo, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, hi);
}
// Randomized pivot avoids the O(n^2) worst case on sorted/adversarial input.
private static int partition(int[] arr, int lo, int hi) {
int randomIndex = lo + (int) (Math.random() * (hi - lo + 1));
swap(arr, randomIndex, hi);
int pivot = arr[hi];
int i = lo - 1;
for (int j = lo; j < hi; j++) {
if (arr[j] <= pivot) {
swap(arr, ++i, j);
}
}
swap(arr, i + 1, hi);
return i + 1;
}
private static void swap(int[] arr, int a, int b) {
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
// ---- Classic binary search: O(log n) time, O(1) space ----
public static int binarySearch(int[] arr, int target) {
int low = 0, high = arr.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2; // avoids (low+high) overflow
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
// ---- Search on the answer: LeetCode 875, Capacity To Ship Packages Within D Days ----
public static int shipWithinDays(int[] weights, int days) {
int low = Arrays.stream(weights).max().getAsInt(); // any single package must fit
int high = Arrays.stream(weights).sum(); // ship everything in one day
while (low < high) {
int mid = low + (high - low) / 2;
if (daysNeeded(weights, mid) <= days) {
high = mid; // mid works — try to shrink capacity further
} else {
low = mid + 1; // mid too small — need more capacity
}
}
return low; // low == high: smallest feasible capacity
}
private static int daysNeeded(int[] weights, int capacity) {
int days = 1, currentLoad = 0;
for (int w : weights) {
if (currentLoad + w > capacity) {
days++;
currentLoad = 0;
}
currentLoad += w;
}
return days;
}
}Python implementation
import random
def merge_sort(arr: list[int]) -> None:
"""O(n log n) time, O(n) space, stable. Sorts in place."""
if len(arr) < 2:
return
buffer = [0] * len(arr)
_merge_sort(arr, buffer, 0, len(arr) - 1)
def _merge_sort(arr: list[int], buffer: list[int], lo: int, hi: int) -> None:
if lo >= hi:
return
mid = lo + (hi - lo) // 2
_merge_sort(arr, buffer, lo, mid)
_merge_sort(arr, buffer, mid + 1, hi)
_merge(arr, buffer, lo, mid, hi)
def _merge(arr: list[int], buffer: list[int], lo: int, mid: int, hi: int) -> None:
buffer[lo:hi + 1] = arr[lo:hi + 1]
i, j, k = lo, mid + 1, lo
while i <= mid and j <= hi:
if buffer[i] <= buffer[j]:
arr[k] = buffer[i]
i += 1
else:
arr[k] = buffer[j]
j += 1
k += 1
while i <= mid:
arr[k] = buffer[i]
i += 1
k += 1
while j <= hi:
arr[k] = buffer[j]
j += 1
k += 1
def quick_sort(arr: list[int]) -> None:
"""O(n log n) average, O(n^2) worst case, in-place, not stable."""
_quick_sort(arr, 0, len(arr) - 1)
def _quick_sort(arr: list[int], lo: int, hi: int) -> None:
if lo >= hi:
return
pivot_index = _partition(arr, lo, hi)
_quick_sort(arr, lo, pivot_index - 1)
_quick_sort(arr, pivot_index + 1, hi)
def _partition(arr: list[int], lo: int, hi: int) -> int:
# Randomized pivot avoids the O(n^2) worst case on sorted/adversarial input.
random_index = random.randint(lo, hi)
arr[random_index], arr[hi] = arr[hi], arr[random_index]
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
def binary_search(arr: list[int], target: int) -> int:
"""O(log n) time, O(1) space."""
low, high = 0, len(arr) - 1
while low <= high:
mid = low + (high - low) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
def ship_within_days(weights: list[int], days: int) -> int:
"""Search on the answer: LeetCode 875."""
low, high = max(weights), sum(weights)
def days_needed(capacity: int) -> int:
trips, current_load = 1, 0
for w in weights:
if current_load + w > capacity:
trips += 1
current_load = 0
current_load += w
return trips
while low < high:
mid = low + (high - low) // 2
if days_needed(mid) <= days:
high = mid # mid works — try smaller
else:
low = mid + 1 # mid too small
return lowship_within_days is the “search on the answer” pattern in miniature: the array of weights is never binary-searched — the capacity is. The feasibility check days_needed(capacity) <= days is monotonic (bigger capacity never needs more days), so the range of possible capacities behaves exactly like a sorted array for binary-search purposes, even though no sorting happened.
Why comparison-based sorting can’t beat O(n log n)
Any comparison-based sort can be modeled as a binary decision tree: each internal node is one comparison (a < b?) with two branches, and each leaf is one final, fully-determined ordering of the input. For n distinct elements there are n! possible orderings, so the tree needs at least n! leaves. A binary tree with n! leaves needs height ≥ log2(n!), and by Stirling’s approximation log2(n!) ≈ n log2 n. So any comparison-based algorithm needs Ω(n log n) comparisons in the worst case — merge sort and heap sort hit this bound exactly. Non-comparison sorts (counting sort, radix sort) can beat it because they never ask “is a < b” — they exploit structure in the values themselves (bounded integer range, fixed digit count).
Binary search: the bounds/midpoint traps
- Overflow:
mid = (low + high) / 2can overflow a 32-bit int whenlow + highexceedsInteger.MAX_VALUE.mid = low + (high - low) / 2avoids it. Irrelevant in Python (arbitrary-precision ints) but a real bug in Java/C++. - Inclusive vs. exclusive bounds:
while (low <= high)withhigh = mid - 1(both bounds inclusive) is the standard “does this exact value exist” search.while (low < high)withhigh = mid(half-open) is the standard shape for boundary-finding searches likeshipWithinDaysabove, where you’re converginglowandhighonto the same answer rather than looking for an exact index. Mixing the two styles in one function is the #1 source of off-by-one infinite loops. - “Search on the answer” generalizes binary search past sorted arrays entirely: whenever you can state a monotonic yes/no predicate over a range of candidate answers (once true, stays true as the candidate increases — or decreases), you can binary search the boundary where the predicate flips, instead of scanning every candidate linearly.
Complexity comparison
| Algorithm | Best | Average | Worst | Space | Stable? | In-place? |
|---|---|---|---|---|---|---|
| Bubble 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 (aux array) |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) stack | No | Yes |
| Heap sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | Yes |
| Binary search | O(1) | O(log n) | O(log n) | O(1) iterative | n/a | n/a |
Common pitfalls
- Quicksort on sorted/nearly-sorted input without randomization: always picking the first or last element as pivot degrades to O(n²) on already-sorted data — a common adversarial test case. Randomize the pivot or use median-of-three.
- Running binary search on unsorted data: gives a wrong answer silently — no exception, no crash, just an incorrect result, because the low/high shrinking logic assumes monotonicity that isn’t there.
- Off-by-one on binary search bounds:
while (low <= high)paired withhigh = mid(instead ofmid - 1) can infinite-loop whenlow == high - 1and the predicate keeps choosing the same half. Match the loop condition style to the bound-update style. - Merge sort’s O(n) space getting waved away: fine in an interview, but a real concern for memory-constrained or very large datasets — quicksort or heap sort are the in-place alternatives.
- Search-on-answer with the wrong feasibility direction: get “does this capacity work” backwards (
>=vs<=) and the binary search still terminates, but converges on the wrong boundary. Always verify monotonicity explicitly before trusting the binary search shape.
Practice problems
- Merge Sort / Quick Sort (implement from scratch, both partition and merge steps)
- Binary Search (classic — the base case every variant builds on)
- Search in Rotated Sorted Array
- Find Minimum in Rotated Sorted Array
- Kth Largest Element in an Array (quickselect — a quicksort partition that recurses into only one side)
- Capacity To Ship Packages Within D Days (search on the answer)
- Koko Eating Bananas (search on the answer)
- Median of Two Sorted Arrays (binary search on the partition point — the hardest common variant)
Interview angles
- “Why does the standard library use quicksort-style algorithms over merge sort, despite the worse worst case?” — better cache locality (in-place, sequential-ish access) and lower constant factor in the average case; production sorts are usually hybrids (introsort: quicksort that falls back to heapsort past a recursion-depth threshold; Timsort: merge sort tuned for real-world partially-sorted data).
- “How do you avoid quicksort’s O(n²) worst case?” — randomized pivot selection or median-of-three, so an adversary can’t construct a worst-case input just by knowing the pivot rule.
- “When would you pick merge sort over quicksort?” — when stability matters (preserving relative order of equal keys), or for external sorting where data doesn’t fit in memory (merge sort’s sequential access pattern suits disk/tape merging far better than quicksort’s random access).
- “Is binary search only for sorted arrays?” — no. It works on any monotonic yes/no predicate over an ordered range of candidate answers — “search on the answer” is the generalization, and recognizing it is a genuine differentiator in interviews.
- “What’s the actual lower bound for comparison-based sorting, and why?” — Ω(n log n); decision-tree argument:
n!possible orderings, each comparison is one bit of information (2-way branch), so you need at leastlog2(n!) ≈ n log ncomparisons to distinguish all of them. - “How would you recognize a ‘search on the answer’ problem that doesn’t look like one?” — look for phrasing like “minimum X such that Y is achievable” where checking a single candidate X for feasibility is easy (often a greedy simulation), even though nothing about the input itself is sorted.