A implementação do método Arrays.sort no JDK 8 utiliza uma combinação de algoritmos para otimizar o processo de ordenação, adaptando-se ao tamanho e à estrutura dos dados.

Detecção de Pequenos Conjuntos de Dados

Para arrays de tamanho reduzido, o método emprega uma estratégia diferente:

// Usa Quicksort para arrays pequenos
if (right - left < QUICKSORT_THRESHOLD) { // QUICKSORT_THRESHOLD é 286
  sort(a, left, right, true);
  return;
}

Ao acessar o método sort(a, left, right, true), observa-se a seguinte lógica:

// Usa Insertion Sort para arrays minúsculos
if (length < INSERTION_SORT_THRESHOLD) { // INSERTION_SORT_THRESHOLD é 47
    if (leftmost) {
    // ... implementação específica para o caso mais à esquerda ...
    }
    // ...
}

Se a quantidade de elementos for inferior a 47 (INSERTION_SORT_THRESHOLD), o Insertion Sort é aplicado. Este algoritmo é eficiente para conjuntos de dados pequenos e quase ordenados.

/*
 * Traditional (without sentinel) insertion sort,
 * optimized for server VM, is used in case of
 * the leftmost part.
 */
for (int i = left, j = i; i < right; j = ++i) {
    int ai = a[i + 1];
    while (ai < a[j]) {
        a[j + 1] = a[j];
        if (j-- == left) {
            break;
        }
    }
    a[j + 1] = ai;
}

Ordenação para Conjuntos de Dados Maiores

Para conjuntos de dados maiores que 47, mas ainda abaixo de 286, um algoritmo de Quick Sort é utilizado. A abordagem geral do Quick Sort envolve:

1. Seleção de um elemento pivô a partir do conjunto.
2. Particionamento do array: elementos menores que o pivô são movidos para sua esquerda, e elementos maiores para sua direita. O pivô fica em sua posição final.
3. Chamadas recursivas para ordenar as sub-arrays resultantes.

Tratamento de Dados Quase Ordenados e Adaptação para Merge Sort

Antes de aplicar o Merge Sort em conjuntos de dados com mais de 286 elementos, o sistema verifica se o array apresenta alguma estrutura:

// Verifica se o array está quase ordenado
for (int k = left; k < right; run[count] = k) {
    if (a[k] < a[k + 1]) { // crescente
        while (++k <= right && a[k - 1] <= a[k]);
    } else if (a[k] > a[k + 1]) { // decrescente
        while (++k <= right && a[k - 1] >= a[k]);
        for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
            int t = a[lo]; a[lo] = a[hi]; a[hi] = t;
        }
    } else { // igual
        for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
            if (--m == 0) {
                sort(a, left, right, true); // Retorna para Quicksort se muitos iguais
                return;
            }
        }
    }

    /*
     * O array não é altamente estruturado,
     * usa Quicksort em vez de merge sort.
     */
    if (++count == MAX_RUN_COUNT) { // MAX_RUN_COUNT é 67
        sort(a, left, right, true); // Retorna para Quicksort se a estrutura for quebrada
        return;
    }
}

Esta fase identifica sequências ascendentes ou desecndentes. Cada sequência descendente é revertida para ascendente. Um contador (count) é incrementado para cada sequência encontrada. Se o contador exceder MAX_RUN_COUNT (67), o array é considerado não estruturado e o Quick Sort é novamente selecionado. Caso contrário, se o array possuir alguma estrutura (count < 67), o processo prossegue para o Merge Sort.

A lógica de determinação da base de alternância para a mesclagem é definida:

// Determina a base de alternância para a mesclagem
byte odd = 0;
for (int n = 1; (n <<= 1) < count; odd ^= 1);

Implementação do Merge Sort

A partir daqui, o Merge Sort é executado:

// Mesclagem
for (int last; count > 1; count = last) {
    for (int k = (last = 0) + 2; k <= count; k += 2) {
        int hi = run[k], mi = run[k - 1];
        for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
            if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) {
                b[i + bo] = a[p++ + ao];
            } else {
                b[i + bo] = a[q++ + ao];
            }
        }
        run[++last] = hi;
    }
    if ((count & 1) != 0) {
        for (int i = right, lo = run[count - 1]; --i >= lo;
            b[i + bo] = a[i + ao]
        );
        run[++last] = right;
    }
    int[] t = a; a = b; b = t;
    int o = ao; ao = bo; bo = o;
}

Em resumo, o Arrays.sort do JDK 8 combina Insertion Sort, Quick Sort e Merge Sort de forma adaptativa para oitmizar a performance em diferentes cenários de dados.