Sorting & Searching

Heapsort

An in-place O(n log n) sort built directly on a binary heap — the only elementary comparison sort with both a guaranteed worst case and O(1) extra space, at the cost of poor cache locality.

Build a max-heap from the array in O(n) (Floyd's bottom-up heapify, not n inserts at O(log n))
Repeatedly swap the max to the end and sift-down the reduced heap — n times, O(log n) each
O(n log n) worst case, guaranteed — no adversarial input degrades it
O(1) extra space: the heap lives in the same array being sorted
Not stable, and its array-as-tree access pattern jumps around memory — usually slower in practice than quicksort despite the same asymptotic bound

Heapsort

static void heapSort(int[] a) {
    int n = a.length;
    for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, i, n);   // build max-heap, O(n)
    for (int end = n - 1; end > 0; end--) {
        int tmp = a[0]; a[0] = a[end]; a[end] = tmp;
        siftDown(a, 0, end);
    }
}

static void siftDown(int[] a, int i, int size) {
    while (true) {
        int left = 2 * i + 1, largest = i;
        if (left < size && a[left] > a[largest]) largest = left;
        if (left + 1 < size && a[left + 1] > a[largest]) largest = left + 1;
        if (largest == i) return;
        int tmp = a[i]; a[i] = a[largest]; a[largest] = tmp;
        i = largest;
    }
}

Heapsort vs quicksort vs mergesort
	Heapsort	Quicksort	Mergesort
Worst case	O(n log n)	O(n²)	O(n log n)
Extra space	O(1)	O(log n)	O(n)
Typical speed	slowest of the three	fastest	middle