Power Sort em Java

Pesquisando uma maneira de ordenar números sem usar ifs, acabei tropeçando no Power Sort (e aqui e aqui).

Quando finalmente resolvi escrevê-lo em Java, percebi que era uma variação do Counting Sort. Com quase sete bilhões de pessoas na terra, é difícil ter uma idéia original. De qualquer forma, o Power Sort é um caso especial muito interessante do Counting Sort, porque:

• Usa pouquíssima memória;
• É ainda mais rápido e
• Não precisa de ifs!

O Counting Sort usa um array enquanto o Power Sort usa uma ou duas variáveis numéricas. Por isso, o Power Sort fica restrito a conjuntos menores de dados (para não provocar um overflow).

O código abaixo é o de um Counting Sort muito simples. Ele não considera números negativos e faz a ordenação no mesmo array que recebe.

public class CountingSort {

  public static short[] sort(short[] in) {
    int[] order=new int[32768];
    for(int i=0;i<in.length;i++) {
      order[in[i]]++;
    }
    int index=0;
    int n=0;
    while(n<in.length) {
      while(order[index]==0) {
        index++;
      }
      for(int i=0; i<order[index]; i++) {
        in[n+i]=(short)index;
      }
      n+=order[index];
      index++;
    }
    return in;
  }

}

A idéia é simples. Os shorts positivos vão de 0 a 32767, então o array order representa quantas vezes cada número apareceu em in. Como o índice de order já representa a posição de cada número, só preciso copiar as casas maiores que zero de volta para o array original (as que tem zero representam números que não estão em in).

O interessante desse algorítmo é que ele só precisa olhar para os dados uma vez; ele não precisa de comparações; e tampouco faz trocas. O que ele produz é uma espécie de transformada dos dados.

E o desempenho é excelente. O gráfico abaixo mostra uma comparação com o Quick Sort (através do método Arrays.sort())

No eixo vertical estão os tempos em milissegundos e no eixo horizontal estão as quantidades de elementos ordenados. Testei de um em um milhão até quarenta milhões.