For this final part of the assignment you will write several C++ template functions to sort a list of items using the recursive merge sort algorithm.

Program

Implement the following template functions in a header file called mergesort.h. This header file should have header guards (as usual) and should contain both the prototypes and definitions for the functions.

template void mergeSort(vector& set, bool (*compare)(const T&, const T&))

This function should sort the items in the vector set using the merge sort algorithm. The first argument to this function is a reference to a vector object containing the list of items to sort. The second argument is a pointer to a comparison function that can be used to compare two items of the template type.

This function should call the recursive merge sort function, passing it the vector, the subscript of the first vector element (which is 0), the subscript of the last vector element (which is set.size() - 1), and the pointer to the comparison function (compare), e.g.:

 mergeSort(set, 0, set.size()-1, compare); 

template void mergeSort(vector& set, int low, int high, bool (*compare)(const T&, const T&))

This recursive function divides a vector into two subvectors, sorts them, and then merges the two sorted subvectors.

 int mid; if (low < high) { mid = (low + high) / 2; // Divide and conquer mergeSort(set, low, mid, compare); mergeSort(set, mid+1, high, compare); // Combine merge(set, low, mid, high, compare); } } 

template void merge(vector& set, int low, int mid, int high, bool (*compare)(const T&, const T&))

This function merges two sorted subvectors.

 // Create temporary vector to hold merged subvectors vector temp(high - low + 1); int i = low; // Subscript for start of left sorted subvector int j = mid+1; // Subscript for start of right sorted subvector int k = 0; // Subscript for start of merged vector // While not at the end of either subvector while (i <= mid && j <= high) { if (compare(set[j], set[i])) { Copy element j of set into element k of temp Add one to j Add one to k } else { Copy element i of set into element k of temp Add one to i Add one to k } } // Copy over any remaining elements of left subvector while (i <= mid) { Copy element i of set into element k of temp Add one to i Add one to k } // Copy over any remaining elements of right subvector while (j <= high) { Copy element j of set into element k of temp Add one to j Add one to k } // Copy merged elements back into original vector for (i = 0, j = low; j <= high; i++, j++) Copy element i of temp into element j of set 

A driver program, assign8.cpp, is provided below to test your code for this part of the assignment. A copy of the driver program can also be found on turing at /home/turing/t90kjm1/CS241/Code/Spring2017/Assign8/Part3/assign8.cpp.