Sorting & Searching

Sorting and searching are two of the most fundamental categories of algorithms in computer science, underlying countless other algorithms and everyday software operations.

Common sorting algorithms. Several sorting algorithms are commonly studied, each with different performance characteristics: bubble sort and insertion sort are simple but generally slow for large inputs; merge sort and quicksort are more efficient, generally used in practice for larger datasets; and many programming languages' built-in sort functions use optimized, hybrid approaches under the hood.

Time complexity of sorting. Understanding that different sorting algorithms have different time complexities — some scale poorly as input size grows, while others scale much better — is important context for understanding why certain algorithms are preferred for large datasets despite being more complex to implement.

Binary search. For searching within an already-sorted collection, binary search is a highly efficient technique that repeatedly divides the search range in half, comparing the target value against the middle element and eliminating half of the remaining possibilities each time, rather than checking every element sequentially.

When sorting helps searching. Many problems become much easier to solve efficiently once the input is sorted — for example, binary search only works on sorted data, and various other algorithms rely on a sorted input as a precondition for their efficiency, which is why sorting is often a first step even when the eventual goal is a different operation entirely.

Stability and other sorting properties. Some sorting algorithms are "stable," meaning elements with equal values retain their relative original order after sorting — a property that matters in certain applications where the original order of equal elements carries meaning.

The numbers behind the comparisons. Putting concrete complexities to the algorithms makes the comparison sharper: bubble sort and insertion sort are O(n²) in the average and worst cases, merge sort is O(n log n) in all cases, and quicksort is O(n log n) on average but degrades to O(n²) on adversarial input if pivots are chosen poorly. Insertion sort is nonetheless genuinely fast on small or nearly sorted inputs, which is why production sorts often switch to it for small subranges. Binary search runs in O(log n), which is why it remains fast even as inputs grow enormous — doubling the data adds a single step.

Why O(n log n) is the barrier. Any sorting algorithm that works by comparing pairs of elements cannot do better than O(n log n) in the worst case. The reasoning is counting-based: there are n! possible orderings, each comparison distinguishes at most two branches, and distinguishing n! possibilities therefore requires at least on the order of log(n!) comparisons, which grows as n log n. This is not a limitation of current algorithms but a proven lower bound on the whole approach, which is why no comparison sort will ever be asymptotically faster.

Sorting without comparisons. The bound above applies only to comparison-based sorting, and algorithms that exploit structure in the keys can beat it. Counting sort tallies occurrences of each value and reconstructs the output, running in time proportional to the number of elements plus the range of values; radix sort processes keys digit by digit. Both are linear under the right conditions and useless under the wrong ones — counting sort over a huge value range consumes memory proportional to that range. They illustrate a general principle: knowing something about your data can beat a general-purpose algorithm.

Memory use and stability in practice. Merge sort's guaranteed O(n log n) comes at the cost of O(n) auxiliary memory, while quicksort sorts in place with only logarithmic stack space — a trade-off that often decides which is used where memory is constrained. Stability interacts with this: merge sort is naturally stable, quicksort is not. Stability matters concretely when sorting by successive keys, since sorting by a secondary key and then stably by a primary key produces a correctly ordered result on both, an idiom that silently breaks with an unstable sort.

Binary search beyond sorted arrays. The technique generalizes well past "find this value in this array". Variants find the first or last occurrence of a repeated value, or the insertion point for a value not present. More powerfully, binary search applies to any monotonic predicate — if some property is false up to a threshold and true after it, the threshold can be found in logarithmic time without any array existing at all. This pattern, often called binary searching on the answer, turns many optimization problems ("what is the smallest capacity that works?") into a feasibility check repeated a logarithmic number of times.

Getting binary search right. Binary search is notoriously easy to state and easy to implement incorrectly. The failures are boundary conditions: whether the search range is inclusive or exclusive at each end, whether the midpoint calculation can overflow in fixed-width integer types, and whether each iteration is guaranteed to shrink the range — a loop that fails to make progress hangs rather than returning a wrong answer. The discipline that prevents these is stating the loop invariant explicitly, then verifying by hand on arrays of length zero, one, and two.

What to do in practice. For nearly all production work the correct choice is the language's built-in sort, which is a carefully tuned hybrid that beats a hand-written implementation on both performance and correctness. The skill that transfers is not implementing sorts but knowing what to ask: is the comparator correct and consistent, is stability required, is the input already nearly sorted, and is sorting even necessary — since finding a maximum or the top few elements can be done in linear time without sorting at all.

Understanding both how common sorting algorithms work and when binary search applies is foundational to reasoning about the efficiency of a wide range of other algorithms and data-processing tasks.