Multiple functions are used to help implement this algorithm:

• merge(): merges two halves of an array.

  1. Compares elements of both halves. The smaller element is copied into an auxiliary array. Continue doing so until one of the halves is exhausted. 

  2. Copy any remaining elements from the other half to the auxiliary array, which is now sorted.

  3. Copy the sorted elements back from to the original array. 

• mSort(): divides an array into smaller subarrays, then merges and sorts them.

  1. Recursively divide the array into halves until the subarray is a single element, which is the base case and returns the function. 

  2. Use merge() on the two halves to merge them into a single sorted subarray. Once all the recursive calls are resolved you will end up with one sorted array.

• mergeSort(): entry point for the merge sort algorithm.

  1. Creates an auxiliary array to temporarily hold elements to assist in swapping.

  2. Calls mSort() to start the algorithm.