Probability of Outcomes in Merge Shuffle

[ardentra]

So I've been banging my head on this problem for a few days and haven't gotten very far, hoping someone has some insights. I know this sort of reads like a homework problem, but this problem is the result of personal investigations and does not come from an assignment.

So for those of you who don't know, Merge Sort is an algorithm that works by taking a list of elements to be sorted, L, and splitting L into halves L₁ and L₂, then splitting those halves, repeatedly until reaching a set of lists of length 1. Then the lists are recombined with correct ordering until once again arriving at one list, which is now sorted. Lists are not sets: order matters, and in this case you can only add items onto the front of lists.

So say you had the list of numbers 3,9,8,0,2,1,5,7,4,6. Performing Merge Sort would look like this(I removed commas for convenience):

3980215746

39802 15746

39 802 15 746

3 9 8 02 1 5 7 46

3 9 8 0 2 1 5 7 4 6

39 8 02 15 7 46

39 028 15 467

02389 14567

0123456789

During the merge steps, items are selected one at a time from the left side of both L₁ and L₂, compared to one another, and the item with the smaller value is added to the new list. This step is repeated until the lists have been combined.
So a single merge step would operate like this for lists L₁ = 2,3 and L₂ = 1,4:

Compare 1 and 2
Add 1 to the recombined list
Compare 2 and 4
Add 2 to the recombined list
Compare 3 and 4
Add 3 to the recombined list
Add 4 to the recombined list


So that is Merge Sort. Merge Shuffle works the same way, except that during the recombining stage, there is a 50% chance of a number being taken from L₁ and a 50% chance of a number being taken from L₂ for addition to the recombined list.
So combining lists L₁ = 1,2 and L₂ = 3,4 might operate like this:

Select 1 or 3
Add 3 to the recombined list
Select 1 or 4
Add 1 to the recombined list
Select 2 or 4
Add 4 to the recombined list
Add 2 to the recombined list

Which would create the newly shuffled list L = 3142.

I am fairly sure that at a single add step during a merge, the probability of an element at position e in list E = E₁... ...E_n of length n ending up in position t of the target list T = T₁, T₂... where x positions in T have already been filled and d = t - x is equal to:

if e > d then probability = 0
if e + o < d then probability = 0
otherwise probability = .5^d

Where o is the number of items remaining in the other list being merged.

So this is the question I want to solve: Given input list I of length n, and I containing no repeated items, what is the probability that performing Merge Shuffle on I produces I as the result?

And more generally, given input list I of length n, and I containing no repeated items, what is the probability of producing the given result L ≠ I?

 

[mfb]

If n is a power of 2, this looks easy to analyze.
If n is not, that looks ugly - you have to keep track of all combinations of k with k+1 elements somewhere. Let f(I) be the result of a merge shuffle. I think f(I)=I can be studied with some casework (look at n=2, n=3, n=4, n=5, ..., try to find a recursion formula), but I don't know how to get the more general result.