Freezesort

You are given an array $A = 8 , 3 , 2 , 4 ,5 , 6 , 7 , 1 ,9,10,11,12,13$ of size $$n$$. As long as the array is not sorted, in each step, a subset of $$A$$ is randomly permuted. This subset is optimally chosen each time so that $$A$$ is sorted in the least amounts of steps. What is the expected value of the total number of times this operation needs to be done in order to sort $$A$$?

×