### Question:
RadixSort { public static void radixSort(int[] input, int n, int[] scratch, int[] countScratch) { if (countScratch.length != 65536) throw new IllegalArgumentException("countScratch.length must be = 65536"); if (input.length < n) throw new IllegalArgumentException("input.length must be >= n"); if (scratch.length < n) throw new IllegalArgumentException("scratch.length must be >= n"); Arrays.fill(countScratch, 0); for (int i = 0; i < n; i++) countScratch[input[i]&0xFFFF]++; int sum = 0; for (int i = 0; i < countScratch.length; i++) { int temp = sum; sum += countScratch[i]; countScratch[i] = temp; } for (int i = 0; i < n; i++) { int temp = input[i]&0xFFFF; int offset = countScratch[temp]++; scratch[offset] = input[i]; } Arrays.fill(countScratch, 0); for (int i = 0; i < n; i++) countScratch[(scratch[i]>>16)+32768]++; sum = 0; for (int i = 0; i < countScratch.length; i++) { int temp = sum; sum += countScratch[i]; countScratch[i] = temp; } for (int i = 0; i < n; i++) { int temp = (scratch[i]>>16)+32768; int offset = countScratch[temp]++; input[offset] = scratch[i]; } }  static void radixSort(int[] input, int n, int[] scratch, int[] countScratch);  }### Answer:
@Test public void test() { Random r = new Random(); final int n = 10000000; int[] test1 = new int[n]; int[] test2 = new int[n]; int[] scratch = new int[n]; int[] countScratch = new int[65536]; for (int z = 0; z < 10; ++z) { for (int i = 0; i < n; i++) { int x = r.nextInt(); test1[i] = x; test2[i] = x; } long elapsed = -System.currentTimeMillis(); Arrays.sort(test1); elapsed += System.currentTimeMillis(); System.out.println("quicksort elapsed = "+elapsed+"ms"); elapsed = -System.currentTimeMillis(); RadixSort.radixSort(test2, n, scratch, countScratch); elapsed += System.currentTimeMillis(); System.out.println("radixsort elapsed = "+elapsed+"ms"); for (int i = 0; i < n; i ++) { assertEquals(test1[i], test2[i]); } } }