Which sorting algorithm would be good for sorting small-sized integer arrays and why? What is the performance? What about for large-sized integer arrays?

Question

Which sorting algorithm would be good for sorting small-sized integer arrays and why?  What is the performance? What about for large-sized integer arrays?

JG · Accepted Answer

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.

Pavel · Answer

Small: Insertion Sort
Large: Tim Sort or some other variation of n log n sort that switches to Insertion Sort when depth is too high / short subarray.

wqj · Answer

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

wqj · Answer

for large-sized integer arrays, should use bucket sort

Amazon

Question d’entretien chez Amazon

Réponses aux questions d'entretien

Entreprises suivies

Recherche d’emplois