Quick Sort vs Radix Sort

Question

In an coding exam, I was once asked this question:

Assuming that you are only sorting Integers in ascending order, which algorithm do you use when you want to prioritize speed the most, but you also want to save space?

The options were:

• LSD Radix Sort
• Merge Sort
• Quick Sort

I think an argument can be made between LSD Radix Sort and Quicksort.

Radix sort would function in $O(k n)$ and Quicksort would function in $O(n \log n)$ and worst case, $O(n^2)$

I chose Radix Sort as the answer, but I'm curious as to what others had to say.

Answer 1

This depends... If the number of input numbers is $n$, assuming the word-ram model of computation, a word size of $\Theta(\log n)$ bits, and worst-case inputs:

• Radix sort would require $O(n \log n)$ time and $O(n)$ auxiliary space.

• Quicksort with fixed or random pivot selection would require $O(n^2)$ worst-case time and $O(\log n)$ auxiliary space.

• Mergesort requires $O(n \log n)$ time and $O(n)$ auxiliary space.

Radix sort and Merge sort are then equivalent in this setting.

Notice that using quicksort with random pivoit selection results in a time complexity of $O(n \log n)$ with high probability. Selecting the pivot deterministically in a way that partitions the elements into two sets whose cardinalities are at most a constant factor apart gives your an algorithm with worst-case time complexity of $O(n \log n)$ and $O(\log n)$ auxiliary space.