Searching is one of the most fundamental algorithmic tasks. Linear search examines every item one by one, giving a time complexity of \(O(n)\). Binary search repeatedly divides a sorted array's search interval in half, achieving a time complexity of \(O(\log n)\) but requiring sorted input. Interpolation search improves on binary search for uniformly distributed sorted arrays by guessing where the key likely resides based on its value, while exponential search enables binary search on a sorted, unbounded list by first determining a bracketing range in exponential steps. Ternary search is a divide-and-conquer algorithm that locates the maximum or minimum of a unimodal function by dividing the search space into three parts. For the more specialized task of finding the kth smallest element in an unordered list, QuickSelect is related to quicksort and has an average time complexity of \(O(n)\). The Boyer-Moore majority vote algorithm finds an element appearing more than \(n/2\) times in \(O(n)\) time and \(O(1)\) space, and Kadane's algorithm finds the maximum sum of a contiguous subarray in linear time. For spatial problems, flood fill is an algorithm that determines the area connected to a given node in a multi-dimensional array, classically used in the bucket fill tool of paint programs, and the Lee algorithm is a possible solution for maze routing problems that always gives an optimal solution if one exists, at the cost of being slow and memory intensive.
Sorting algorithms arrange data in a particular order, typically numerical or lexicographical, and they fall into comparison-based and non-comparison-based families. Bubble sort repeatedly swaps adjacent elements that are out of order, with a best case of \(O(n)\) when the array is already sorted. Selection sort selects the smallest unsorted element in each iteration and places it at the front. Insertion sort builds the final sorted array one item at a time, and Shell sort is a variation that allows exchanges of far-apart elements to reduce the number of movements. Merge sort is a divide-and-conquer algorithm that splits the input in half, recursively sorts each half, and merges them, achieving \(O(n \log n)\) in all three cases. Quick sort is also divide-and-conquer, choosing a pivot and partitioning the array around it, with a worst case of \(O(n^2)\) typically when the input is sorted or reverse-sorted and the pivot is chosen poorly. Heap sort uses a heap to repeatedly extract the maximum element into the sorted region.
Non-comparison-based sorts and hybrid sorts fill out the landscape. Counting sort counts objects with distinct key values, hashing-like, and works when keys fall within a specific range. Radix sort is non-comparative and distributes elements into buckets according to their radix, repeating the bucketing process for each digit while preserving prior ordering. Bucket sort is most useful when input is uniformly distributed over a range, such as floating-point numbers in \([0.0, 1.0)\). Cycle sort is an in-place, unstable comparison sort that is theoretically optimal in the total number of writes to the original array. Modern languages rely heavily on hybrid sorts: TimSort, used as the standard sort in Python and Java, combines merge sort and insertion sort to perform well on real-world data, and Introsort begins with quicksort, switches to heapsort when recursion depth exceeds a threshold, and finishes small subarrays with insertion sort, providing both fast average and optimal worst-case performance. Beyond sorting and searching, classical number-theoretic algorithms include the Sieve of Eratosthenes for finding all primes up to a given limit, the Euclidean algorithm for computing the greatest common divisor of two integers, and modular exponentiation, which performs exponentiation over a modulus and is fundamental to public-key cryptography. The Fast Fourier Transform computes the discrete Fourier transform in \(O(n \log n)\) rather than \(O(n^2)\), Catalan numbers enumerate many recursive structures such as valid parenthesis sequences and full binary trees, and reservoir sampling draws a simple random sample of k items from a population of unknown size in a single pass. Cycle detection in linked lists is performed by Floyd's Tortoise and Hare algorithm, with Brent's algorithm providing a generally faster alternative of the same worst-case complexity, and Gaussian elimination solves systems of linear equations and computes ranks, determinants, and inverses of matrices.