Power Sort em Java II

Tendo percebido (e logo relevado) que Power Sort é um caso especial do Counting Sort, decidi continuar investindo neste ramo da tecnologia ifless.

Começando pelo caso mais simples (ordenar apenas números inteiros sem repetições), encontrei uma solução muito simples com a classe BigInteger.

public static void psort(int[] in) {
    BigInteger TWO=new BigInteger("2");
    BigInteger pp=BigInteger.ZERO;
    for(int i=0; i<in.length; i++) {
     pp=pp.add(TWO.pow(in[i]));
    }    
    
    for(int i=0; i<in.length; i++) {
     in[i]=pp.getLowestSetBit();
     pp=pp.flipBit(in[i]);
    }
}

O código funciona em duas etapas. Na primeira, o número pp recebe cada elemento do array in como uma potência de 2. Ou seja, pp+=2^in[i]. Na segunda parte, a posição do i-ésimo bit indica o valor da i-ésima casa do array já ordenado. Como não há um método para percorrer os bits 1, uso o método flipBit() para negar o primeiro e fazer do próximo o primeiro.

O código abaixo mostra um teste com um pequeno array de 200 posições.

import java.math.BigInteger;

public class PowerSort {

  public static void psort(int[] in) {
    BigInteger TWO=new BigInteger("2");
    BigInteger pp=BigInteger.ZERO;
    for(int i=0; i<in.length; i++) {
     pp=pp.add(TWO.pow(in[i]));
    }    
    
    System.out.println(pp);
    
    for(int i=0; i<in.length; i++) {
     in[i]=pp.getLowestSetBit();
     pp=pp.flipBit(in[i]);
    }
  }
  
  public static void main(String... args) {
    int[] test=new int[200];
    for(int i=0;i<200;i++) {
      test[i]=200-i;
    }    
    psort(test);
    for(int i : test) {
      System.out.printf("%d ", i);
    }
    System.out.println();
  }

}

O array começa com os valores 200 a 1 e os ordena para a ordem crescente. O valor final de pp é o respeitável e impronunciável

3213876088517980551083924184682325205044405987565585670602750

Quanto maiores os números, tanto maior ficará pp e, portanto, mais memória será usada para executar a ordenação. Se os valores forem conhecidos de antemão, será muito mais econômico usar um mapa de bits.