Sorting an array of strings by length in linear complexity

Question

I am trying to find an algorithm to sort an array of strings by length in O(n) time complexity, and O(1) space complexity. The max length of the strings is known. Because of that, I tried using counting sort, but I failed to do in O(1) space complexity. Because multiple strings might have the same length, I need to store the strings in some kind of 2D array for each possible length, and that is O(n) space in the worst case of all strings having the same length. How would I go about solving this problem?

Answer 1

Assume the maximum length of strings is $k$, which is less than some constant.

Here is a simple algorithm that runs in linear time and $O(1)$ space complexity. The strategy is simply counting strings by length followed by in-place rearrangement.

Assume the input is an array $s[0], s[1], \cdots, s[n-1].$

1. Count the number of strings of length $i$. Store it in $a[i]$. We can imagine that $s$ is split into $k+1$ blocks of size $a[0], a[1], a[2], \cdots$. In the following steps, the $i$-th block will store the strings of length $i$.
2. Let $b$ be the partial sums of $a$, i.e., $b[0]=0$, $b[i+1]=b[i]+a[i]$ for all $0\le i\le k-1$. Note that $b[i]$ is the index of the first string in the $i$-th block.
3. Let $t[0], t[1], t[2],\cdots,$ be an array of $k$ numbers. We will use $t[i]$ to track the next available position to settle the next string of length $i$. Initially, $t$ is a clone of $b$.

4. Let $j=0$, the index of the first unsettled string. Loop the following.

   Suppose the length of $s[j]$ is $i$.

   • If $j\neq t[i]$, switch $s[j]$ and $s[t[i]]$. Now $s[t[i]]$ is a settled string. Increase $t[i]$ by 1.

   • If $j= t[i]$, increase $t[i]$ by 1. Keep increasing $j$ until either we find the next unsettled string or we have passed all strings, in which case we return $s$ and stop the algorithm.

     How can we increase $j$ efficiently and correctly? We can keep another integer that tracks which block $j$ is in. Note that all strings from index $b[i]$ to $t[i]-1$ inclusive are settled while all strings from index $t[i]$ to $b[i+1]-1$ inclusive are not settled.

It is clear the algorithm runs in linear time. The spaces used besides the original array $s$ are arrays $a,$ $b$ and $t,$ several looping variables, one temporary place needed to switch two strings. In total, the working memory is less than $3(k+1)+c+k=O(1)$.

Exercise. Improve the memory usage of the algorithm by reusing array $a$ for $b$.