In, say, classical Radix Sort implementation we start to sort an array of integers from the right to the left, that is starting from LSD. My question is, should we even sort the leftmost column if at the next iteration all its values will be sorted again? Can one start sorting from the second column from the end?

You can find example of what I've meant at this page: https://s3.stackabuse.com/media/articles/radix-sort-in-python-4.png

EDIT: rightmost, but not leftmost.

CodePudding user response：

Not the leftmost but rightmost (Least Significant Digit).

Yes, we must sort by the rightmost digit at the first stage because at the second stage we consider only the second digit.

For example, if we have [15 13] array and want to sort by the second digit (second from the right - 1's) only - there is no need to swap elements (looking at equal 1's), and array remains the same - unsorted...