<p>I have a idea of how mergesort works, but I'm not sure how mergesort works starting in the part where the two subarrays are sorted. </p>
<p>I don't understand how the two subarrays pair themselves into one. One idea I have in mind is to do a comparison of the two arrays, see which one is smaller, and put that into the first element back to the first array, but that sounds like selection sort. </p>
<p>Can someone help me with this? Here is a summary of what i mean:</p>
<pre><code>If the list is of length 0 or 1, then it is already sorted. Otherwise:
Divide the unsorted list into two sublists of about half the size.
Sort each sublist recursively by re-applying the merge sort.
Merge the two sublists back into one sorted list.
</code></pre>
<p>I understand everything but the last two.</p>
<p>Thanks!</p>
<p>I think all you need to know that it’s faster than quadratic sorts, and it takes an average of nlogn times where n is the number of things to be sorted. </p>
<p>I didn’t even bother trying to understand the things behind it sorry 
</p>
<p>Someone else help me and him/her out?</p>
<p>Step 3 is the recursive call. You’ve just divided your original list into two smaller lists. You call MergeSort() on each of those smaller lists; since the lists are smaller, the “magic” of recursion will allow them to be sorted.</p>
<p>So, now to step 4. You have two small lists, each of which is sorted. Now, you need to make one big sorted list out of them. That’s what the merge operation does.</p>
<p>Take some playing cards and grab just the cards with numbers with one suit (say, clubs). Suppose you want to sort them. Divide the pile of cards into two smaller piles and sort them (any way you like). Now, how can you create one big sorted pile out of the two smaller sorted piles?</p>
<p>a. The top card on each smaller pile is obviously the smallest of that pile. So, to find the smallest of all the cards, all you have to do is pick the smallest of those two top cards. Take the smaller one and start a new pile with it.</p>
<p>b. Now, you still have two piles left, but one of the cards is different. Repeat step a; pick the smallest of the two top cards and set it aside.</p>
<p>c. Continue until … well, when do you think you should stop? And what do you do to finish up afterwards?</p>