sort n integers of range 0~n^2-1 in O(n) time

This is one problem introduced in "Introduction to Algorithm".

We can use radix-sort to solve it.

?

package alg;import java.util.ArrayList;import java.util.Iterator;/* * This example shows how to use radix sort algorithm to sort N integers in the range of 0 ~ N^2-1. */public class RadixSortExample {    void sort(int a[], int N){        int len = a.length;                ArrayList<ArrayList<Integer>> bucket= new ArrayList<ArrayList<Integer>>(N);        for(int i = 0; i<N;i++){            bucket.add(new ArrayList<Integer>(len));        }        ArrayList<Integer> temp = new ArrayList<Integer>(len);                for(int i = 0; i< len; i++){            temp.add(new Integer(a[i]));        }        for(int i = 0; i<len; i++){            int digit0 = temp.get(i).intValue() % N;            bucket.get(digit0).add(temp.get(i));        }        temp.clear();                for(int i = 0; i<N; i++){            Iterator<Integer> it = bucket.get(i).iterator();            while(it.hasNext()) temp.add(it.next());        }        for(int i = 0; i<N;i++){            bucket.get(i).clear();        }        for(int i = 0; i<len; i++){            int digit1 = temp.get(i).intValue() / N;            bucket.get(digit1).add(temp.get(i));        }        temp.clear();        for(int i = 0; i<N; i++){            Iterator<Integer> it = bucket.get(i).iterator();            while(it.hasNext()) temp.add(it.next());        }        Iterator<Integer> it = temp.iterator();        while(it.hasNext()) System.out.println(it.next());            }    /**     * @param args     */    public static void main(String[] args) {        // TODO Auto-generated method stub        int a []= {63,20,43,15,56,9,1,28};        RadixSortExample r = new RadixSortExample();        r.sort(a,8);    }}

?