バケットソートを紹介します。

このソートは要素の値の範囲が決まっている配を高速に並び替えるのに役立ちます。汎用のソートアルゴリズム(要素の値の範囲が決まっていないソート)では多くの場合、計算量はO(nlogn)であるのに対し、このソートではO(n)で計算できます。

ただし、要素の値が取り得る値の範囲の数だけの格納領域が必要です。例えば、要素に対する仮定が 「int 型の整数である」というだけであるとするとその取り得る値の範囲は0～4294967296の約43億個分の整数を格納する領域が必要になります。

以下はバケットソートの特に分布数えソートと呼ばれるアルゴリズムのJavaのサンプルです。

BucketSort.java

package sort;

import java.util.Arrays; 
import java.util.Random;
public class BucketSort {
  public static int[] sort(int[] src, final int RANGE) {
    int[] offsets = new int[RANGE];
    for (int i : src) {
      offsets[i]++;
    }
    int n = 0;
    for (int i = 0; i < offsets.length; i++) {
      int t = n + offsets[i];
      offsets[i] = n;
      n = t;
    }
    assert(n == src.length);

    int[] dst = new int[src.length];
    for (int i : src) {
      dst[offsets[i]++] = i;
    }
    return dst;
  }

  public static void main(String[] args) {
    final int RANGE = 100;
    Random random = new Random();
    int[] vec = new int[1024];
    for (int i = 0; i < vec.length; i++) {
      vec[i] = random.nextInt(RANGE);
    }
    System.out.println(Arrays.toString(vec));
    System.out.println(Arrays.toString(sort(vec, RANGE)));
  }
}