/** 製品 Class (test) */
public class TestGoods {
    public int price;       /// 値段
    public String name; /// 製品名
    public TestGoods next;  /// 次の TestGoods への片方向リンク

    /** コンストラクタ */
    public TestGoods(int price) {
        this.price = price;
        next = null;
    }
}

/** TestGoods の配列 */
public class TestGoodsArray {
    public TestGoods start; // 片方向リンクの開始object
    public TestGoods last;  // 最後にあるobject
    public int size;

    /** コンストラクタ */
    public TestGoodsArray() {
        clear();
    }
    /** 中身を空にする */
    public void clear() {
        start = null;
        last = null;
        size = 0;
    }
    /** 要素を追加 */
    public boolean add(TestGoods goods) {
        size++;
        if (start == null) {
            start = goods;
            last = goods;
            return true;
        }
        last.next = goods;  // リンクを繋げる
        last = goods;
        return true;        // (一応、Collection.add の汎用規約どおり)
    }
    /** 要素同士を繋げる */
    public void connect(TestGoodsArray link) {
        if (link == null) { return; }
        if (start == null) {
            start = link.start;
            last = link.last;
            size = link.size;
            return;
        }
        size += link.size;
        last.next = link.start;
        last = link.last;
    }
}

/**
 * 基数ソート （int を、8ビット毎 4桁として処理する）
 * 一般的な基数ソートに比べて、メモリを多く取ることはありません。
 * その代償として、元の配列を書き換えます。
 * */
public class BitRadixSort {
    TestGoodsArray[] bucket = new TestGoodsArray[256];  /// 桁のバケツ

    /** コンストラクタ */
    public BitRadixSort() {
        for (int i = 0; i < 256; i++) {
            bucket[i] = new TestGoodsArray();
        }
    }

    /**
     * @param array ソートしたい配列。配列は直接書き換わります。
     * @return  ソートにかかった時間 (nano seconds)
     */
    public long sort(TestGoodsArray array) {
        long stTime = System.nanoTime();        // 処理計測用
        int bitShift = 0;
        TestGoods link;
        int maxVal = Integer.MIN_VALUE;
        int i;
        int cnt = 4;        // 最大チェック桁数 = 4
        do {
            // bucket のクリア
            for (i = 0; i < 256; i++) {
                bucket[i].clear();
            }
            link = array.start; // 配列の最初から
            // 値の桁に対するバケツに入れていく
            if (cnt == 4) {
                // ループの最初だけ、最大値を求める。また、ループの最初は bitShift をしなくても良い。
                do {
                    int a = link.price;
                    if (a > maxVal) { maxVal = a; }
                    TestGoods linkOld = link;
                    bucket[a & 255].add(linkOld);   // 桁のバケツに入れる
                    link = link.next;       // 次の link へ
                    linkOld.next = null;    // バケツに入れた link は切る
                } while (link.next != null);
            } else {
                // 2回目以降のループ
                do {
                    int a = link.price;
                    TestGoods linkOld = link;
                    bucket[(a >> bitShift) & 255].add(linkOld); // 桁のバケツに入れる
                    link = link.next;       // 次の link へ
                    linkOld.next = null;    // バケツに入れた link は切る
                } while (link.next != null);
            }
            // バケツを繋いでいって配列を作る
            array.clear();  // array は一旦、空にする
            for (i = 0; i < 256; i++) {
                if (bucket[i].start != null) {
                    array.connect(bucket[i]);
                }
            }
            array.last.next = null; // 念のため

            bitShift += 8;  // 次の8ビットへ

            if (cnt == 4) {     // 最初のループだったら、値の最大値によってループ回数を小さくする
                if ((maxVal & 0xff000000) == 0) {
                    cnt--;
                    if ((maxVal & 0xff0000) == 0) {
                        cnt--;
                        if ((maxVal & 0xff00) == 0) {
                            cnt--;
                        }
                    }
                }
            }
        } while (--cnt > 0);

        return System.nanoTime() - stTime;      // かかった時間を返す
    }
}

import java.util.*;

public class BitRadixTest {
    static final int N = 10000;     /// 配列の大きさ
    static final int VARMAX = 0x01000000;   /// 配列の中身の取り得る最大値

    /** main */
    public static void main(String[] args) {
        int i;
        TestGoodsArray array_Radix = new TestGoodsArray();  // BitRadix sort 用配列を確保
        ArrayList<TestGoods> array_Csort = new ArrayList<TestGoods>(N); // Collections.sort 用配列を確保
        Random rnd = new Random();

        // テストデータの作成 (0 以上 VARMAX 未満の、ランダムな値で埋める)
        for (i = 0; i < N; i++) {
            int val = rnd.nextInt(VARMAX);
            array_Radix.add(new TestGoods(val));    // テスト用2つの配列に同じ値をセット
            array_Csort.add(new TestGoods(val));
        }

        // BitRadix sort
        BitRadixSort radix = new BitRadixSort();
        long time_bitRadix = radix.sort(array_Radix);

        // Csort
        long stTime = System.nanoTime();
        Collections.sort(array_Csort, new Comparator<TestGoods>() {
            public int compare(TestGoods obj1, TestGoods obj2) {
                return obj1.price - obj2.price;
            }
        });
        long time_Csort = System.nanoTime() - stTime;

        // データの検証
        int lastVal = Integer.MIN_VALUE;
        TestGoods link = array_Radix.start;
        do {
            int val = link.price;
            if (val < lastVal) {
                System.out.println("\nError !! (last=" + lastVal + ", val=" + val);
            }
            //System.out.print(val + ", "); // 配列の内容を表示したい時はコメントを外す
            lastVal = val;
            link = link.next;
        } while (link != null);
        //System.out.println("");   // 配列の内容を表示したい時はコメントを外す
        System.out.println("Radix time  = " + time_bitRadix + " ns");
        System.out.println("Arrays time = " + time_Csort + " ns");
    }
}