Sorting transforms random data into ordered data — and ordered data is fundamentally easier to work with. Once an array is sorted, binary search finds any element in O(log n) instead of O(n). Duplicate detection becomes a single linear scan of adjacent elements. The "merge intervals" pattern (LC 56) only works if intervals are sorted by start time. The "two-sum" pattern has an O(n) two-pointer variant that requires sorted input. In interviews, sorting is rarely the entire problem — it's the enabling first step that simplifies everything after it. The theoretical lower bound for comparison-based sorting is Ω(n log n) — no comparison sort can beat this in the worst case. Merge Sort and Heap Sort achieve this bound with guaranteed O(n log n). Quick Sort achieves O(n log n) average but O(n²) worst case with poor pivot selection. Non-comparison sorts (Counting Sort, Radix Sort, Bucket Sort) beat this bound by exploiting integer properties, achieving O(n+k) where k is the value range — but they only apply to integers within a bounded range. Java's Arrays.sort() uses Dual-Pivot Quick Sort for primitives and TimSort (merge sort variant) for objects — in interviews, call Arrays.sort() and focus on the actual problem, not reimplementing sort.

Bubble Sort and Selection Sort are O(n²) algorithms that nobody uses in production — but they appear on interview conceptual questions and are useful for understanding sorting invariants. Know them conceptually; never implement them when asked to "sort efficiently."

Insertion Sort builds the sorted portion one element at a time — pick the next unsorted element and insert it into the correct position by shifting larger elements right. It's O(n²) worst case but O(n) on already-sorted or nearly-sorted data, making it the optimal algorithm for small arrays and the finishing step inside hybrid sorts like TimSort. Every hand of cards you've ever sorted was insertion sort — pick up a card, slide it into position among the cards you already hold.

Merge Sort is the divide-and-conquer sorting algorithm: split the array in half, recursively sort each half, then merge the two sorted halves in O(n). It gives a guaranteed O(n log n) worst case — no bad inputs can make it degrade. The merge step is the key insight: merging two sorted arrays into one sorted array costs O(n) using two pointers. The trade-off is O(n) auxiliary space for the merge buffer. Merge Sort is stable (equal elements maintain relative order) and is the foundation of Java's Arrays.sort() for objects (TimSort), external sorting (sorting data too large for RAM), and the "count inversions" interview pattern.

Quick Sort picks a pivot element, partitions the array into elements less than and greater than the pivot, then recursively sorts each partition. Average case O(n log n) with excellent cache performance — in practice, often faster than Merge Sort despite the same asymptotic complexity. The danger: if the pivot is always the smallest or largest element (e.g., first element on already-sorted input), partitions are maximally unbalanced → O(n²). Mitigation: random pivot selection or median-of-three. Quick Sort is in-place (O(log n) stack space) and is the basis of Java's Arrays.sort() for primitives (Dual-Pivot Quick Sort). Not stable.

Build Merge Sort and Quick Sort from scratch once — it makes the mechanics concrete. In any real interview, call Arrays.sort() and focus on the actual problem.

Most interview problems don't ask you to implement a sorting algorithm — they ask you to sort first, then solve the real problem using the sorted order. "Merge Intervals" sorts by start time then merges overlapping intervals. "Meeting Rooms" sorts by start time to find conflicts. "Kth Largest Element" uses Quick Select or a heap. The sorting step is O(n log n) preprocessing that enables an O(n) solution. Recognise the signal: when order doesn't matter in the input but would simplify the logic, sort first.

→ See all Sorting problems with full solutions