Sorting an array of strings by length in linear complexity
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].$


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$.

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.
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$.
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$.