カウントソート

値の幅が広いから使えない、で終わりではありません。桁ごとに分けて同じことを繰り返せば基数ソートになり、大きな整数でも比較なしで並びます。