Recall Merge Sort sorts a vector of elements. Rewrite Merge Sort to sort a list of elements. You may use your own List or STL list. This must be in C++.

Write your own version of merge_sort(), merge(), and copy() functions.Do not use generic functions such as sort(), inplace_merge(), merge() or copy().

Do not use STL list methods such as sort() or copy(). Make sure the time complexity of your merge_sort() function is in O(n log n).

Make sure you take care of end conditions such as sorting a null list or a list of one element.

Give your own simple main() function that constructs a list, calls your merge sort, and prints the sorted sequence.