Probability of partially sortedness of a perfectly shuffled array of unique numbers

Question

Sorry that I don't know any better way to express this question.

Assuming that we have a perfectly shuffled array of unique numbers, we know that the array is in fact consisted of ascending or descending sorted subarrays. In average howmany such sorted subarrays consist this one particular perfectly shuffled array is the question.

As a simple example, please consider an array of 20 integers [0...19] shuffled as [14,2,5,16,18,19,7,6,12,17,3,4,8,11,15,13,1,0,9,10] which is internally sorted in chunks as [[14,2],[5,6,18,19],[7,6],[12,17],[3,4,8,11,15],[13,1,0],[9,10]] so in total we obtain 7 subarrays.

Now this observation just paves the way for a very efficient sorting algorithm once you merge them cleverly.

Yet it's even better than that. I naively assumed that the number of subarrays in average should be like half the length of the initial array (50% sorted internally). But no, that's only the worst case which you very rarely get. It's like hitting 10101010 or 01010101 in 8 bits. So for 8 bits per se the chance of hitting worst case is $2\times\frac{1}{2^8} = \frac{1}{128}$. Similarly hitting the best case where we end up with only one subarray (given the shuffled array is already sorted ascending or descending) should have the same chance (or is it?). As a result, in average we get better than 50% internal sorting but howmuch better? In my tests I have observed that in average a perfectly shuffled array of unique items turns out to be ~58.68% sorted internally. In other words a 1000 item array would yield in average ~410 sorted subarrays to merge.

While my algorithm seems just fine, perhaps it misses some edge cases. I would appreciate helps to know if this 58.68% figure is inline with the math of it.

Edit: To gain further insight, I have decided to add some more observations when repeatition is allowed.

• 2 choices in n length array i.e. (0,1) yields 75% (25 subarrays from 100 items array)
• 3 choices in n length array (0,1,2) yields 67.28%
• 4 choices in n length array yields 64.385%
• 13 choices yields %60.06
• n choices in n length array yields 58.68% (same as no repetition)

Answer 1

I can prove that, as $n\to\infty$, the expected number of sorted sub-arrays in a random permutation of length $n$ grows asymptotically like $$ \big(1+2\cdot (\tan 1-\sec 1)\big)n\approx 0.4132\,n $$ Note that $1-0.4132=0.5868$, which matches the $58.68\%$ figure from your simulations.

Proof: Let the random permutation be $a=(a_1,a_2,\dots,a_n)$. Call $a_k$ a leader if it is the first entry of a sorted subarray. The number of subarrays equals the number of leaders, so to find the expected number of subarrays, we can add up the probabilities of each entry being a leader.

For each $k\in \{1,\dots,n\}$, let us find the probability that $a_k$ is a leader. Certainly, for $k\ge 4$, we know $a_k$ is a leader if one of these two events occurs: $$ a_{k-3}<a_{k-2}<a_{k-1}>a_k\qquad\text{or}\qquad a_{k-3}>a_{k-2}>a_{k-1}<a_k\tag1 $$ The probability of the first event is $$ \mathrm P(a_{k-3}<a_{k-2}<a_{k-1}>a_k)=\frac1{3!}-\frac1{4!}=\frac18=12.5\%, $$ and symmetrically the same is true for the other event, so the probability $a_k$ is a leader is at least $2\cdot 12.5\%=25\%$. However, there are other ways $a_k$ can be a leader. If $k\ge 6$, then $a_k$ is a leader as long as $$ \color{blue}{a_{k-5}<a_{k-4}<a_{k-3}}>\color{purple}{a_{k-2}<a_{k-1}} > \color{red}{a_k}\tag2 $$ This happens with probability $$ \mathrm P(a_{k-5}<a_{k-4}<a_{k-3}>{a_{k-2}<a_{k-1}}>a_k)=\frac{1}{3!}\cdot \frac1{2!}-\frac1{3!}\cdot \frac1{3!}-\frac1{5!}+\frac1{6!}\approx 4.86\% $$ Again, we need to multiply this by $2$ to account for the upside-down version of this situation. So far, the accumulated probability is $25\%+9.72\%\approx 34.7\%$.

In general, call a sequence alternating if every entry is either larger than its two neighbors, or smaller than its two neighbors. Then

$a_k$ is a leader if and only if the longest contiguous alternating sub-array ending with $a_k$ has odd length.

For example, if $(1)$ occurs, the maximal alternating subarray ending with $a_k$ is $(a_{k-2},a_{k-1},a_k)$, which has length $3$. If $(2)$ occurs, the maximal alternating subarray is $(a_{k-4},a_{k-3},a_{k-2},a_{k-1},a_k)$, with length $5$.

Let $A_n$ be the number of alternating permutations of length $n$ (note: my definition of $A_n$ gives double the number of Wikipedia's definition, since I allow both up-down-up-... and down-up-down-...). The probability that $a_k$ ends a maximal alternating sub-array of length $3$ is $A_3/3!-A_4/4!=25\%$, while the probability that the length is $5$ is $A_5/5!-A_6/6!=9.72\%$, and so on. The total probability that $a_k$ is a leader is $$ \frac{A_3}{3!}-\frac{A_4}{4!}+\frac{A_5}{5!}-\frac{A_6}{6!}+\dots\tag{$*$} $$ Technically, for $a_k$, the sum in $(*)$ should only include $k-2$ terms, but this does not matter in the limit as $n\to\infty$. André showed that, for any $x\in \mathbb C$ such that $|x|<\pi/2$, $$ \sum_{n\ge 0}A_n\frac{x^n}{n!}=2(\tan x+\sec x) $$ Letting $x=-1$, and rearranging, the sum of the series in $(*)$ is $$ -2(\tan(-1)+\sec(-1))+\frac{A_0}{0!}-\frac{A_1}{1!}+\frac{A_2}{2!}=1+2(\tan 1-\sec 1) $$ Since the probability of each $a_k$ being a leader is $1+2(\tan1-\sec 1)$, the expected number of sorted sub-arrays is $n$ times that probability.