Merge Sort

O Merge sort divide um array em metades, ordena-as recursivamente e intercala os dois intervalos ordenados. Seu tempo de execução previsível e sua estabilidade o tornam um algoritmo fundamental de ordenação por comparação.

static void mergeSort(int[] values) {
    int[] buffer = new int[values.length];
    mergeSort(values, buffer, 0, values.length);
}

private static void mergeSort(int[] values, int[] buffer, int low, int high) {
    if (high - low < 2) return;
    int middle = low + (high - low) / 2;
    mergeSort(values, buffer, low, middle);
    mergeSort(values, buffer, middle, high);
    merge(values, buffer, low, middle, high);
}

private static void merge(
        int[] values, int[] buffer, int low, int middle, int high) {
    System.arraycopy(values, low, buffer, low, high - low);
    int left = low;
    int right = middle;
    for (int destination = low; destination < high; destination++) {
        if (left >= middle) values[destination] = buffer[right++];
        else if (right >= high) values[destination] = buffer[left++];
        else if (buffer[left] <= buffer[right]) values[destination] = buffer[left++];
        else values[destination] = buffer[right++];
    }
}

Correção

Use indução sobre o comprimento do intervalo. Intervalos de comprimento zero ou um estão ordenados. Supondo que as duas chamadas recursivas ordenem suas metades menores, o laço de intercalação mantém o invariante de que o prefixo da saída contém, em ordem, os menores elementos já consumidos. Ao término, o intervalo inteiro está ordenado e contém exatamente os elementos originais.

Complexidade

A recorrência T(n) = 2T(n/2) + Θ(n) resulta em tempo Θ(n log n) em todos os casos. O buffer compartilhado usa espaço auxiliar Θ(n), e a recursão usa Θ(log n) quadros de pilha. O pico de espaço auxiliar é Θ(n), não Θ(n log n). Esta implementação é estável porque, em caso de empate, primeiro retira o elemento da metade esquerda, mas não é in-place.