Merge Sorting is an essential way to sort arrays. Merge Sort is a divide and conquer algorithm. It divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves.
The following is a pseudocode for the algorithm:
MergeSort(arr[], l, r) If r > l 1. Find the middle point to divide the array into two halves: middle m = l+ (r-l)/2 2. Call mergeSort for first half: Call mergeSort(arr, l, m) 3. Call mergeSort for second half: Call mergeSort(arr, m+1, r) 4. Merge the two halves sorted in step 2 and 3: Call merge(arr, l, m, r)
Please implement a function to execute the merge sort algorithm.
You will be given an integer M which corresponds to the size of the array to be sorted, followed by M number of integers which are the contents of the array.
Integer M (1 <= M <= 100 000)
M numbr of integers. (all integers will be able to fit in an int variable)
The contents of the array followed by a newline character.