Is this modified Radix sorting algorithm valid?

Question

A friend and I were discussing the following problem and had two differing opinions. Who is correct here and why? The problem is as follows:

Consider a modification of the radix-sort algorithm, in which we use Quick-Sort to sort each of the digits. Is this algorithm a valid sorting algorithm? If the answer is no, explain why. If the answer is yes, explain what is its best-time complexity of the modification? Your answer should depend on , The number of digits needed to represent each number in the array.

My friend believes that it is not a valid sorting algorithm because quicksort is unstable and radix sort is stable. I believe it's possible (although pointless) and would have a best-case runtime of log d of n.

Answer 1

In the ^th pass, radix sort would place numbers in buckets based on the ^th digit of each number and so arrive at an order of the numbers by their ^th digit.

There are at least two versions of radix sort:

1. One where the digits are visited from least significant to most significant, each time (re)distributing them over the ten buckets and collecting them again in the order in which they appear from bucket 0 to bucket 9

2. One where the digits are visited from most significant to least significant, where -- if a bucket has more than one number -- the procedure is repeated separately for the numbers in that bucket, using the next digit.

The first variant only works correctly if the distribution into buckets is stable, i.e. where numbers that arrive in the same bucket, maintain their relative order with respect to the previous pass.

There is no such requirement for the second variant.

Secondly, there exist quicksort variants that are stable, but if we assume that an unstable variant of quicksort is used to sort the numbers by their ^th digit, instead of using the buckets, then we can state the following:

• If the first version of radix sort is used, then an unstable sorting method for the sorting by the ^th digit will not be reliable, and can produce wrong results:

  For instance, if we have =2 and input 31, 32 then the first pass will will sort the numbers by their final digit, which gives 31, 32. The second pass will sort the numbers by their first digit, and if the unstable aspect of the chosen comparison sort kicks in, this may produce 32, 31 as output, which obviously is not the desired result.

• If the second version of radix sort is used, then even an unstable comparison-based sorting method can be used for the sorting by the ^th digit, and the results will be correct, but not necessarily stable.

  The time complexity will suffer, as in the first pass all digits (of that many numbers) are sorted by a comparison-based sorting algorithm. Quick sort has an average (not worst) time complexity of O(log). So the first pass has an average time complexity of O(log), the second O(10((/10)log(/10))), then O(10²((/10²)log(/10²))), ... etc ( passes)

  Summing up, gives O((log + log(/10) + ... + log(/10⁻¹)).

  Let's say = 1000 and for simplicity we choose the base of the log as 10, then the inner expression is 3+2+1+0 (or fewer terms if is relatively small compared to ). We can see that this is a triangular number, and so we can arrive at O(log²) for that inner expression, giving a total average time complexity of O(log²).