Lab: Merge Sort

A Useful Algorithm to Analyze

Unlike bubble sort and selection sort, which are simple to code, merge sort is actually used in practice. The algorithm for merge sort is fairly easy to understand, although implementing it takes a bit more work.

In order to sort a list...

1. Divide it in the middle into two equal lists
2. Call another function (recursion!) to sort each of the two lists
3. Merge together the two sorted lists you get back

I already provided you functions to append and print a list, to make life easier. More ways to simplify (break down) the problem

• Write a function to return the length of a list
• Write a function that takes two sorted lists and returns a pointer to a single, merged list
• Recognize the base case for the recursive call: when you are asked to sort a list of length 1, you simply return that same list

Check out the starting code file here. There are instructions in the file for how you need to be able to sort two different ways (by age and by last name). Make sure to have good tests in main that show that your code works!

https://cssvn.utrgv.edu/svn_etomai/201720_2380/lab06_mergesort/<your username>

If you missed lab, note that the Person class is missing its constructors, and the function operator<< that takes a Person object is missing the ending line:

return out;

Commit your work at the end of lab for lab credit!