Merge

NOTE: If you took CS115 last semester, you may have already done the following part of the assignment. I recommend that you do it again without looking at your solution from last semester. Then, when you have it working, you might want to compare.

1.

Using the pseudocode in Section 12.5, write the method called merge. Be sure to test it before trying to use it as part of a mergeSort.

2.

Write the simple version of mergeSort, the one that divides the deck in half and then uses sortDeck to sort the two halves. Then it uses merge to create a new, fully-sorted deck.

Remember that sortDeck is a modifier and mergeSort is a function, which means that they get invoked differently:

sortDeck (deck);              // modifies existing deck
deck = mergeSort (deck);      // replaces old deck with new

3.

Write the fully recursive version of mergeSort.