It occurred to me today that "Stalin Sort" is related to the Stirling numbers of the first kind, really obvious when you think about it, actually.
Stalin sort is the sorting algorithm that goes as follows. Go down the line and shoot (remove) any element that is not in order. What remains is trivially sorted.
If you are sorting a list with unique entries, i.e., a permutation, then any permutation can be put into a special form (Foata's fundamental bijection https://en.wikipedia.org/wiki/Permutation#Foata's_transition_lemma) where you represent it as cycles where each cycle has its maximum displayed first, and the cycles are arranged in increasing order of those (example below from wikipedia)
Permutation matrix:
\(\begin{smallmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 3 & 7 & 5 & 9 & 1 & 6 & 8 & 2 & 4\end{smallmatrix}\)
In cycle form:
\((5 1 3) (6) (8 2 7) (9 4)\)
This means that to each permutation, the sequence you would get by stalin sort is the same sequence as you would get by viewing it as a permutation written in this form.
The (unsigned) Stirling numbers \(s(n,k)\) of the first kind are used to count permutations according to how many cycles they have.
https://en.wikipedia.org/wiki/Stirling_numbers_of_the_first_kind
If we sum over all permutations we get \(s(n+1,2)\) (OEIS A000254), so the expected length of a permutation of length \(n\) after the gunnery squad has performed their duty is \(\dfrac{s(n+1, 2)}{n!} = H_n\)
Figured this was too short for a blog post.
#combinatorics #sorting