1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Quicksort does require $O(\log n)$ extra space, regardless of recursive/iterative implementation (you need to keep track of the ranges; if you do the longer one immediately and postpone the shorter one each time, you need at most $\log_2 n$ ranges to register, ironically the worst space usage is in the best case time-wise). $\endgroup$ – vonbrand Apr 12 at 17:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.