Heap Sort

O Heap sort constrói um max-heap e move repetidamente sua raiz máxima para o final do prefixo ainda não ordenado.

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;
}

A construção bottom-up do heap é Θ(n). As n - 1 remoções custam O(log n) cada; portanto, o tempo total é Θ(n log n) em todos os casos. Esta implementação usa espaço auxiliar Θ(1) e não é estável. O Heap sort oferece um limite forte de pior caso, mas em geral possui localidade menos favorável que um QuickSort bem implementado.