Merge Sort
if sz of list <= 1 DONE
recursively sort first half
recursively sort second half
merge two halves together

Program 2:  Do lines 3 and 4 in parallel.  Most everyone got this.

Recursively merge.


1.  If I know my position in the list I'm in, I know how many elements come before me in the list I'm in.  If I'm at position 5, then five elements come before me in my own list.

So, I figure out where I would be in the OTHER list, if I had been in that list, and I use binary search to figure this out.  So, if 4 elements come before in the OTHER list, and five come before me in my own list, then nine come before me total, so I should end up in position 9.  All of the elements in in either list should be using this strategy, binary search on the other list, to find their own location in the merged list.

Two tricky points:  what if there are ties?

Well, if I'm in the first list, my element should come before all equal elements in the second list.  If I'm in the second list, my element should come after all equal elements in the first list.  So your binary search should reflect this.  You could use a second method for the slightly different binary search, but I just used a parameter to handle ties.

(Some people had their binary search slightly wrong in the first place.)

Second point:  Once you have all the elements in their proper position in the merged list, you still have copy them back to the original list.  And this should also be done in parallel.