CMPT 225 Lab 6: Mergesort

You are to implement the merge sort algorithm 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, high)

Merge

Merge will take two sorted subarrays of arr (one with indices from low to mid, and the other from mid+1 to high), and merge them into one sorted array. That sorted array is then copied back into arr, overwriting the two subarrays that are now merged.

merge(arr, low, mid, high)
	create a temporary array of size high - low + 1
	initialize indexes (the first subarray starts at low, the second at mid+1, and the temporary starts at 0.)


	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's and temp's indexes
		else			
			insert subarray2's next element in temp
			increment subarray2's 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's and temp's indexes
	
	copy temp into 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 marks 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