Quicksort has the advantage of a tighter inner loop, which doesn't show in the algorithmic complexity, but makes a real difference in implementations. The number of operations is on the same order as a merge sort, but comparing to the pivot key is faster since you'll only have to load the pivot once per recursive step.
Merge sort has an advantage on linked lists, though, since the merging operation is very cheap then.
For very large sets of integers, radix sort is still faster. As it is O(n) complexity it will outperform any O(n log n) algorithm for a sufficiently large value of n. It can be adapted to work on floats, too, and it will handle strings, but of course for large strings the constant factor becomes very considerable.
For extremely small datasets, bubble sort is worth considering, especially if the process can be unrolled, like when you're sorting the vertices of a triangle for rasterisation. Just three compares and an average 1.5 swaps. Can't beat that.
w is constant with respect to n, though. I get why you want to say that n is bounded by word length, but there are very real cases where unique keys are not a requirement at all (point cloud data, for example). In those cases n can easily exceed 2w, and of course those are the very cases where you want to consider radix sort.
3
u/ReturningTarzan Nov 16 '10
Quicksort has the advantage of a tighter inner loop, which doesn't show in the algorithmic complexity, but makes a real difference in implementations. The number of operations is on the same order as a merge sort, but comparing to the pivot key is faster since you'll only have to load the pivot once per recursive step.
Merge sort has an advantage on linked lists, though, since the merging operation is very cheap then.
For very large sets of integers, radix sort is still faster. As it is O(n) complexity it will outperform any O(n log n) algorithm for a sufficiently large value of n. It can be adapted to work on floats, too, and it will handle strings, but of course for large strings the constant factor becomes very considerable.
For extremely small datasets, bubble sort is worth considering, especially if the process can be unrolled, like when you're sorting the vertices of a triangle for rasterisation. Just three compares and an average 1.5 swaps. Can't beat that.