Sorting variable-length items / Algorithms

Question

I have been studying for my Algorithms midterm and there is this question in the book that I came across about sorting variable length items :

• You are given an array of strings, where different strings may have different numbers of characters, but the total number of characters over all the strings is n. Show how to sort the strings in O(n) time.

I found many answers online but they weren't very clear in their explanations so I would really appreciate it if you could take the time to explain to me more in depth what this answer suggests should be done to sort the strings in O(n) time:

1. Groups the strings by length and order the groups
2. Starting i on the maximum length and going down to 1, perform counting sort on the ith character. Make sure to include only groups that have an ith character. If the groups are subsequent subarrays in the original array, we’re perform

Answer 1

This is what you are searching for:https://en.wikipedia.org/wiki/Radix_sort

In simple words:

You start sorting by the first digit of the strings. This can be done in one pass O(N), since you do not need to compare each element with others. You just need to remember the starting and ending position of each group of values in the array. For example all strings starting with 'g' are located in array positions 35 to 500. When you find a string stating with 'g' you add it to the end of this group.

In the next phase you do the same for each of these groups.

As you can see, it takes O(M*N) where M is the string length and N is the number of strings. In your case your N is total length of all strings so it's O(N).

Although you have strings in different lengths you can still keep the O(N), because at some point items that are too short will not need to be re-sorted.