You are to implement the merge sort algorithm covered in class to
sort arrays of integers.

Start by downloading the
zipfile. It contains:

- merge_sort.cpp, which you should fill in
- A makefile.
- test.py and a set of *.in and *.gt input and ground truth files

## MergeSort Algorithm

Here is a brief pseudocode version of the mergeSort algorithm and
its helper merge method. You should implement this in merge_sort.cpp.

#### MergeSort

mergeSort(arr, low, high)
// needs base case
mid = (low + high) / 2
mergeSort(arr, low, mid)
mergeSort(arr, mid + 1, high)
merge(arr, low, mid, mid + 1, high)

#### Merge

merge(arr, low, mid, mid + 1, high)
initialize indexes
create temp array of size high - low + 1
while both subarrays contain unmerged elements
if subarray1's next element is less than subarray2's
insert subarray1's next element in temp
increment subarray1 and temp's indexes
else
insert subarray2's next element in temp
increment subarray2 and temp's indexes
while subarray1 contains unmerged items
insert subarray1's next element in temp
increment subarray1 and temp's indexes
while subarray2 contains unmerged items
insert subarray2's next element in temp
increment subarray2 and temp's indexes
copy temp back to the original (sub)array low ... high

## Testing

Test your mergeSort function by running the python script test.py.
Note that the 6th test case contains 1,000,000 integers. O(n log n)
is magic.

uname@hostname: ~$ ./test.py

**Please run this for a TA successfully (6 tests passed, in a "reasonable" amount
of time) to receive your 1 mark for this lab.**

## Debugging

Final versions of your merge and mergeSort functions should not produce
any output to cout, since cout's output is used for correctness checks
by test.py.
If your code fails a test case, you can try running it individually,
and comparing it to the corresponding ground truth file.
E.g. to run test case 1 and examine its ground truth:

uname@hostname: ~$ ./merge_sort < 1.in
uname@hostname: ~$ more 1.gt