Searching and Sorting

This chapter covers the fundamental search and sort algorithms and their implementations in C: linear/binary search, quicksort, mergesort, heapsort, counting sort, and radix sort.

Why This Matters

Search and sort are the most common algorithms. Their complexity, stability, and memory behavior determine performance across virtually every domain. You also need to know when to use the standard library's qsort/bsearch vs. writing your own.

Prerequisites

• c.ds.1 — complexity.

Core Concept

Searching

• Linear search: scan each element. O(n).
• Binary search: repeatedly halve a sorted array. O(log n). Requires sorted

input.

Sorting

Examples

Binary search

int bsearch_int(const int *a, int n, int key)
{
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == key) return mid;
        if (a[mid] < key) lo = mid + 1;
        else              hi = mid - 1;
    }
    return -1;
}

Quicksort (Lomuto partition)

static void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; }

static int partition(int *a, int lo, int hi)
{
    int pivot = a[hi], i = lo;
    for (int j = lo; j < hi; j++)
        if (a[j] < pivot) swap(&a[i++], &a[j]);
    swap(&a[i], &a[hi]);
    return i;
}

void quicksort(int *a, int lo, int hi)
{
    if (lo < hi) {
        int p = partition(a, lo, hi);
        quicksort(a, lo, p - 1);
        quicksort(a, p + 1, hi);
    }
}

Mergesort

void merge(int *a, int lo, int mid, int hi, int *tmp)
{
    int i = lo, j = mid + 1, k = lo;
    while (i <= mid && j <= hi) tmp[k++] = a[i] <= a[j] ? a[i++] : a[j++];
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= hi)  tmp[k++] = a[j++];
    for (i = lo; i <= hi; i++) a[i] = tmp[i];
}

How It Works

Binary search halves the range each step. Quicksort partitions around a pivot; mergesort recursively splits and merges; heapsort uses a heap (c.ds.8); counting sort counts occurrences; radix sort sorts digit-by-digit.

Variations

Standard library

qsort (unstable, O(n log n) typical) and bsearch (O(log n)) are in <stdlib.h>. They operate on void * with a comparator, so they are generic but not type-safe.

Stability

Stability preserves the relative order of equal elements, which matters for multi-key sorts. Mergesort and counting/radix are stable; quicksort/heapsort are not.

Common Mistakes

• Using (lo + hi) / 2 which can overflow (use lo + (hi - lo) / 2).
• Choosing a bad pivot (first/last on sorted input → O(n²)).
• Forgetting the base case in recursion.
• Not allocating the temp array for mergesort.

Undefined Behavior

• Reading out of bounds (e.g., wrong partition indices). VERIFIED
• Signed overflow in (lo + hi). VERIFIED

Portability

• These algorithms are plain C and portable. qsort/bsearch are standard.

Under the Hood

Sorting performance depends on cache locality and branch prediction. Mergesort is cache-friendly but needs O(n) space; quicksort is in-place but can degrade; heapsort is in-place but cache-unfriendly.

Practical Usage

• Use qsort/bsearch for general-purpose needs.
• Use mergesort when stability or worst-case O(n log n) is required.
• Use counting/radix sort for integer keys with bounded range.

Exercises

1. Implement linear and binary search; test binary search edge cases. 2. Implement quicksort, mergesort, and heapsort. 3. Implement counting sort for non-negative integers. 4. Compare stability by sorting pairs by one key and observing equal-key order.

Deep Challenge

Implement an introspective sort (introsort): quicksort that switches to heapsort when recursion depth exceeds O(log n). Explain how it achieves O(n log n) worst case while keeping quicksort's average speed.

Related Concepts

• c.ds.8 — heapsort.
• c.ds.2 — dynamic arrays.
• c.alg.2 — recursion.

References

• CLRS, Sedgewick; ISO C §7.22.5 (qsort/bsearch).

Verification

• Complexity table and algorithm semantics. VERIFIED
• qsort is not stable. VERIFIED
• No example was executed during generation unless noted. `Execution not

verified.`

Progress

• [ ] Read
• [ ] Understand
• [ ] Complete examples
• [ ] Complete exercises
• [ ] Complete deep challenge

Concept checkboxes

• [ ] Linear and binary search
• [ ] Quicksort
• [ ] Mergesort
• [ ] Heapsort
• [ ] Counting and radix sort

Mastery levels