Sorting Searching

Sorting & Searching Algorithms

Overview

Sorting and searching are among the most fundamental operations in computer science. Knuth dedicated the entirety of The Art of Computer Programming, Volume 3: Sorting and Searching to these topics, reflecting their importance and depth. This skill covers the major algorithms in both categories, their complexities, and guidance on when to use each.

Sorting Algorithms

Comparison Sorts

Comparison-based sorts determine order by comparing pairs of elements. The theoretical lower bound for comparison sorting is O(n log n).

Quicksort

• Strategy: Divide and conquer. Pick a pivot, partition the array so elements less than the pivot come before it and elements greater come after, then recurse.
• Time: O(n log n) average, O(n^2) worst case (poor pivot choice)
• Space: O(log n) stack space (in-place partitioning)
• Stable: No
• Best for: General-purpose sorting; fastest in practice for most data distributions due to excellent cache behavior.

QUICKSORT(A, lo, hi):
    if lo < hi:
        p = PARTITION(A, lo, hi)
        QUICKSORT(A, lo, p - 1)
        QUICKSORT(A, p + 1, hi)

PARTITION(A, lo, hi):
    pivot = A[hi]
    i = lo - 1
    for j = lo to hi - 1:
        if A[j] <= pivot:
            i = i + 1
            swap A[i] and A[j]
    swap A[i + 1] and A[hi]
    return i + 1

Mergesort

• Strategy: Divide and conquer. Split the array in half, recursively sort each half, then merge the two sorted halves.
• Time: O(n log n) in all cases
• Space: O(n) auxiliary
• Stable: Yes
• Best for: When stability is required, linked lists, external sorting (large files that do not fit in memory).

MERGESORT(A, lo, hi):
    if lo < hi:
        mid = (lo + hi) / 2
        MERGESORT(A, lo, mid)
        MERGESORT(A, mid + 1, hi)
        MERGE(A, lo, mid, hi)

MERGE(A, lo, mid, hi):
    create temporary arrays L = A[lo..mid], R = A[mid+1..hi]
    i = 0, j = 0, k = lo
    while i < |L| and j < |R|:
        if L[i] <= R[j]:
            A[k] = L[i]; i++
        else:
            A[k] = R[j]; j++
        k++
    copy remaining elements of L or R into A

Heapsort

• Strategy: Build a max-heap from the array, then repeatedly extract the maximum to build the sorted result.
• Time: O(n log n) in all cases
• Space: O(1) (in-place)
• Stable: No
• Best for: When guaranteed O(n log n) is needed without extra memory. Not cache-friendly, so often slower than Quicksort in practice.

Insertion Sort

• Strategy: Build the sorted array one element at a time by inserting each element into its correct position among the already-sorted elements.
• Time: O(n) best case (nearly sorted), O(n^2) worst/average case
• Space: O(1) (in-place)
• Stable: Yes
• Best for: Small arrays, nearly sorted data, online sorting (data arrives one element at a time). Often used as the base case in hybrid sorts.

Timsort

• Strategy: Hybrid of Mergesort and Insertion sort. Identifies natural runs (already sorted subsequences), extends them with insertion sort, then merges runs using an optimized merge procedure.
• Time: O(n) best case (already sorted), O(n log n) worst case
• Space: O(n) auxiliary
• Stable: Yes
• Best for: Real-world data that often contains partially sorted subsequences. Default sort in Python and Java.

Linear Sorts

These sorts exploit constraints on the input (bounded range, integer keys) to beat the O(n log n) comparison lower bound.

Counting Sort

• Strategy: Count occurrences of each value, then compute positions from cumulative counts.
• Time: O(n + k) where k is the range of input values
• Space: O(n + k)
• Stable: Yes
• Best for: Small integer ranges (e.g., sorting grades 0-100, characters).

Radix Sort

• Strategy: Sort by each digit/character position from least significant to most significant, using a stable sub-sort (typically counting sort) at each position.
• Time: O(d * (n + k)) where d is the number of digits and k is the radix
• Space: O(n + k)
• Stable: Yes
• Best for: Fixed-length integers or strings with bounded alphabet.

Bucket Sort

• Strategy: Distribute elements into buckets based on value range, sort each bucket individually, then concatenate.
• Time: O(n + k) average when input is uniformly distributed; O(n^2) worst case
• Space: O(n + k)
• Stable: Depends on bucket sort
• Best for: Uniformly distributed floating-point numbers in a known range.

Sorting Complexity Comparison

When to Use Which Sort

Searching Algorithms

Binary Search

• Precondition: Array must be sorted.
• Strategy: Repeatedly halve the search space by comparing the target to the middle element.
• Time: O(log n)
• Space: O(1) iterative, O(log n) recursive

BINARY_SEARCH(A, target):
    lo = 0, hi = len(A) - 1
    while lo <= hi:
        mid = lo + (hi - lo) / 2
        if A[mid] == target:
            return mid
        else if A[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1  // not found

Variations: Lower bound (first occurrence), upper bound (last occurrence), search on answer (binary search the solution space).

Interpolation Search

• Precondition: Array must be sorted and values uniformly distributed.
• Strategy: Estimate the position of the target based on its value relative to the min and max of the current range.
• Time: O(log log n) average for uniformly distributed data, O(n) worst case
• Best for: Large, uniformly distributed sorted datasets.

Two Pointers Technique

• Strategy: Use two pointers (indices) that move through the data structure, typically from opposite ends or at different speeds.
• Time: Typically O(n)
• Common applications: Pair sum in sorted array, removing duplicates, partitioning, palindrome check, merging sorted arrays.

Sliding Window Technique

• Strategy: Maintain a window (contiguous subarray) that slides through the array, expanding or shrinking to satisfy a condition.
• Time: Typically O(n)
• Common applications: Maximum/minimum subarray of size k, longest substring without repeating characters, smallest subarray with sum >= target.

Searching Complexity Comparison

Stability in Sorting

A sort is stable if elements with equal keys retain their original relative order after sorting. Stability matters when:

• Sorting by multiple keys (sort by secondary key first, then by primary key with a stable sort).
• Preserving meaningful insertion order.
• Composing sorts for multi-level ordering.

Best Practices

• Use your language's built-in sort (typically Timsort or Introsort) unless you have a specific reason not to -- they are highly optimized.
• For searching in a sorted collection, always prefer binary search over linear search.
• Consider the two pointers technique before reaching for nested loops on sorted data.
• The sliding window technique converts many O(n^2) brute-force subarray problems into O(n).
• When data has bounded integer keys, consider counting or radix sort for linear-time performance.
• Reference Knuth's TAOCP Vol. 3 for rigorous analysis of any sorting or searching method.