CMPT 225 Lab 6: Mergesort

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