Countdown Sort

Resolvi tentar melhorar o Sleep Sort contando alguma coisa diferente e mais rápida que o tempo. A minha primeira idéia foi contar números e usar os próprios elementos desordenados como medida. Então, cheguei ao Countdown Sort.

A idéia é muito simples: subtraio 1 de cada elemento e a ordenação ocorre naturalmente ao passo que os números forem alcançando o zero. O desempenho é terrível, mas o algoritmo é meu e está pago. Além disso, ele não faz nem comparações nem trocas de elementos e isso já é interessante por si só.

Eis o código em Java:

  public static short[] countdownSort(short in[]) {
    short[] order=new short[in.length];
    int index=0;
    short delta=0;
    do {
      for(int i=in.length-1; i>=0; i--) {
        if(in[i]-delta==0) {
          order[index]=in[i];
          index++;
        }
      }
      delta++;
    } while(index<in.length);
    return order;
  }

Um possibilidade interessante é a de implementá-lo em código de máquina, já que todas as CPUs têm instruções para subtrair 1 e comparar com 0. Parece-me que o código seria bem pequeno.

Um pequeno teste mostra que o algoritmo funciona mesmo com elementos repetidos:

  public static void main(String... args) {
    short[] ordered=countdownSort(new short[] {
       2, 40, 33, 1, 100, 4, 2, 0, 0, 1024
    });
    for(short v: ordered) {
      System.out.printf("%d,", v);
    }
  }

%java CountdownSort
0,0,1,2,2,4,33,40,100,1024,

Agora, tenho que achar uma maneira de acelerar a contagem.