Heap Sort

Heap sort builds a max-heap and repeatedly moves its maximum root to the end of the unsorted prefix.

static void heapSort(int[] values) {
    for (int root = values.length / 2 - 1; root >= 0; root--) {
        siftDown(values, root, values.length);
    }
    for (int end = values.length - 1; end > 0; end--) {
        swap(values, 0, end);
        siftDown(values, 0, end);
    }
}

private static void siftDown(int[] values, int root, int size) {
    while (2 * root + 1 < size) {
        int child = 2 * root + 1;
        if (child + 1 < size && values[child + 1] > values[child]) child++;
        if (values[root] >= values[child]) return;
        swap(values, root, child);
        root = child;
    }
}

private static void swap(int[] values, int a, int b) {
    int temporary = values[a];
    values[a] = values[b];
    values[b] = temporary;
}

Bottom-up heap construction is Θ(n). The n - 1 removals cost O(log n) each, so total time is Θ(n log n) in all cases. This implementation uses Θ(1) auxiliary space and is not stable. Heap sort offers a strong worst-case bound but generally has less favorable locality than well-engineered QuickSort.