There is a pogramming meme called Stalin sort which works as follows: the algorithm proceeds from left to right and each time it encounters a value $a_i$ less than the previous one $a_{i-1}$ the element $a_i$ is removed from the sequence.
Visualization of Stalin sort can be found here.
My question is, given a positive integer $n$ what is the expected length of the Stalin-sorted permutation of the sequence $1,...,n$ (we treat all these permutations as equally probable).
I tried to calculate it mathematically but things got messy. Then I wrote code to find out the expected length. Here are the first several values:
| n | expeceted resulting sequence length |
|---|---|
| $1$ | $1$ |
| $2$ | $1.5$ |
| $3$ | $1.8333333333333333$ |
| $4$ | $2.0833333333333335$ |
| $5$ | $2.283333333333333$ |
| $6$ | $2.45$ |
| $7$ | $2.592857142857143$ |
| $8$ | $2.717857142857143$ |
| $9$ | $2.828968253968254$ |
| $10$ | $2.9289682539682538$ |
Given $n$ and $k\in\left[n\right]$, denote by $R_{k}$ the even that the $k^{\text{th}}$ entry of a permutation $\sigma\colon\left[n\right]\to\left[n\right]$ chosen uniformly at random is retained by this sort. Then it follows from linearity of expectation that the desired expected length is \begin{align*} \mathbb{E}\left(\sum_{k\in\left[n\right]} \mathbb{1}_{R_{k}}\right)\ &=\ \sum_{k\in\left[n\right]} \mathbb{E}\left(\mathbb{1}_{R_{k}}\right)\\ &=\ \sum_{k\in\left[n\right]} \mathbb{P}\left(R_{k}\right)\\ &=\ \sum_{k\in\left[n\right]} \frac{\left(k-1\right)!}{k!}\\ &=\ \sum_{k\in\left[n\right]} \frac{1}{k}\\ &=\ \log\left(n\right)+\gamma+o\left(1\right)\text{.} \end{align*}