# Probability of Outcomes in Merge Shuffle

1. Jun 28, 2013

### 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 L1 and L2, 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 L1 and L2, 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 L1 = 2,3 and L2 = 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 L1 and a 50% chance of a number being taken from L2 for addition to the recombined list.
So combining lists L1 = 1,2 and L2 = 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 = E1... ...En of length n ending up in position t of the target list T = T1, T2... 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 = .5d

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 LI?

Last edited: Jun 28, 2013
2. Jun 29, 2013

### Staff: Mentor

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.