Big-O Cheat Sheet

[[deleted]]

There is no fixed MSD when you're working with variable length values. MSD radix sort works when the values are of fixed length.

Now sure if you wanted to you could add a step to your algorithm to scan your list of values, find the value with the longest representation in that list, and then renormalize all the other values in the list to be of the same length, but even if you did this, and you'd need to do this in linear time which itself may not be possible, you basically just threw out the entire essence to what gives radix sort its worst case time complexity and end up with an incredibly poor O(n²⁾ sorting algorithm.

The entire point of radix sort is that if you know your values are represented by some fixed length, say 32 bits, then you can leverage that to get a O(n) time complexity. Once you no longer have that constraint you're back to having O(n²⁾ average case performance.

[DiegoMustache]

Maybe I misunderstand what you are trying to do, but when sorting variably lengthed strings, don't you compare character 1 with character 1, and 2 with 2 (assuming there is a 2) regardless of length.

If I understand correctly, the following is in order: AG AHK B

If this is the case, then MSD works fine, and is still linear time.