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.(adsbygoogle = window.adsbygoogle || []).push({});

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 splittingLinto halvesLand_{1}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._{2}

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 bothLand_{1}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._{2}

So a single merge step would operate like this for listsL= 2,3 and_{1}L= 1,4:_{2}

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 fromLand a 50% chance of a number being taken from_{1}Lfor addition to the recombined list._{2}

So combining listsL= 1,2 and_{1}L= 3,4 might operate like this:_{2}

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 listL= 3142.

I am fairly sure that at a single add step during a merge, the probability of an element at positionein listE=E... ..._{1}Eof length_{n}nending up in positiontof the target listT=T,_{1}T... where_{2}xpositions inThave already been filled andd=t-xis equal to:

ife>dthen probability = 0

ife+o<dthen probability = 0

otherwise probability = .5^{d}

Whereois the number of items remaining in the other list being merged.

So this is the question I want to solve: Given input listIof lengthn, andIcontaining no repeated items, what is the probability that performing Merge Shuffle onIproducesIas the result?

And more generally, given input listIof lengthn, andIcontaining no repeated items, what is the probability of producing the given resultL≠I?

**Physics Forums - The Fusion of Science and Community**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Probability of Outcomes in Merge Shuffle

Loading...

Similar Threads - Probability Outcomes Merge | Date |
---|---|

Taking a mean average of two probabilities to predict an outcome? | Sep 2, 2012 |

Probability question with a definite outcome | Jul 16, 2012 |

Probability of outcome of combined events | Jul 3, 2010 |

Probability of an outcome given multiple attributes | Jun 9, 2010 |

Why do we take the probability of an event ratio as favorable / possible outcome | Jan 6, 2010 |

**Physics Forums - The Fusion of Science and Community**