1
$\begingroup$

I know this is a fairly poorly worded question, but I can't think of a better way to phrase it in the title.

So in Radix Sort, you go digit by digit from least significant to most significant, and along the way you are swapping elements around. When considering the case where two digits are the same, do you look at the original array to decide which should come first, or do you look at the previous iteration?

In one case you would have to store the original to look back on, so my guess is it's not that, but I can't tell which provides the correct result by my own examples. Let me know if I need to describe my question better and I will try.

$\endgroup$
  • $\begingroup$ If we could consult the original array then it wouldn't matter in which order we go over the digits. $\endgroup$ – Yuval Filmus Nov 13 '15 at 12:24
2
$\begingroup$

Radix sort always uses the results of the previous pass, not the original array. It does not attempt to store the original value of the array. You can find a description of radix sort at Wikipedia or in standard algorithms textbooks, and you'll see that it has this property.

As Wikipedia describes, radix sort is stable if you sort the digits starting from least significant and moving on to most significant.

$\endgroup$

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.