Interview Question for Software Engineer at Amazon.com:

for sorting small-sized integer arrays, i think should use Counting sort, it's faster. the performace is O(N+k)

for large-sized integer arrays, should use bucket sort

wqj: bucket sort and counting sort don't rely on the size of the array, but rather the range of integers in the range. Counting sort is O(n) but if it's a 10 element array with the smallest value = 1 and the largest = 1000000, then you will use a 1000000 element temp array. Bucket is also roughly O(n), but if that same 10 element array is between 1 - 4 with repeats, you will get a lot of collisions, and the secondary sorting algorithm can be slow.