Sort and Search

Every mainstream language ships a built-in sort, so why do interviewers keep asking candidates to write one from scratch? Because "implement sort" is really a proxy for three separate skills: can you reason about divide-and-conquer recursion cleanly (merge sort), can you manage in-place partitioning without corrupting the array (quicksort), and can you adapt a textbook algorithm to an unusual data structure or constraint (sorting a linked list with O(1) extra space instead of an array). Interviewers care less about the sorted output and more about whether you can derive the algorithm under pressure and reason about its complexity.

Merge sort vs. quicksort

Merge sort splits the input in half, recursively sorts each half, and merges the two sorted halves back together. It is stable (equal elements keep their relative order), guarantees O(n log n) time in the worst case, and needs O(n) auxiliary space for the merge step on an array — though on a linked list you can merge nodes in place, needing only O(1) extra space beyond the recursion.

Quicksort picks a pivot, partitions the array so smaller elements land left of the pivot and larger ones land right, then recurses on each side. It sorts in place (O(log n) space for the recursion stack) and is usually faster in practice than merge sort due to better cache locality and lower constant factors, but its worst case degrades to O(n^2) if the pivot choice repeatedly produces lopsided partitions (e.g., always picking the first element on already-sorted input). Randomizing the pivot choice makes that worst case vanishingly unlikely.

Quickselect: sorting is overkill for "find the kth"

If you only need the kth largest (or smallest) element, sorting the whole array first is wasteful — it does O(n log n) work to answer a question that doesn't require a total order. Quickselect reuses quicksort's partition step but only recurses into the side that contains the kth index, discarding the other side entirely. On average this halves (or more) the remaining work at each step, giving O(n) average time, though a poor pivot choice can still degrade it to O(n^2) worst case. A binary heap of size k is a solid O(n log k) alternative when you want a worst-case bound instead of an average-case one.