On my search for a fast integer sorting algorithm I came across Radix Sort, which is theoretically faster then quick sort.
So I searched the web for a decent java implementation and came across Erik Gorset's implementation.
While testing I found a bug in the code in that it did not sort the data correctly and that is also did not sort mixed numbers (negative and positive) correctly.
After analyzing and debugging the code I managed to solve the issues.
The fixed up version appears to be 2.5 times faster than quicksort on large data sets (N > 1000) when sorting integers.
| type | size | runs | quick | radix |
|---|---|---|---|---|
| byte | 100 | 1000000 | 1608 | 1451 |
| byte | 1000 | 100000 | 3230 | 624 |
| byte | 10000 | 10000 | 4010 | 515 |
| byte | 100000 | 1000 | 3901 | 515 |
| byte | 1000000 | 100 | 3790 | 702 |
| byte | 10000000 | 10 | 3759 | 827 |
| short | 100 | 1000000 | 1452 | 2340 |
| short | 1000 | 100000 | 3839 | 1263 |
| short | 10000 | 10000 | 6803 | 3432 |
| short | 100000 | 1000 | 8238 | 1732 |
| short | 1000000 | 100 | 7488 | 1607 |
| short | 10000000 | 10 | 6974 | 1856 |
| int | 100 | 1000000 | 1327 | 2340 |
| int | 1000 | 100000 | 3402 | 1357 |
| int | 10000 | 10000 | 6974 | 3526 |
| int | 100000 | 1000 | 8362 | 2949 |
| int | 1000000 | 100 | 9798 | 3884 |
| int | 10000000 | 10 | 11232 | 4617 |
| long | 100 | 1000000 | 1436 | 2403 |
| long | 1000 | 100000 | 4072 | 1373 |
| long | 10000 | 10000 | 7037 | 3556 |
| long | 100000 | 1000 | 8706 | 3167 |
| long | 1000000 | 100 | 10187 | 4649 |
| long | 10000000 | 10 | 11840 | 5367 |