Description
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.
Input
Integer M (1 <= M <= 100 000)
M numbr of integers. (all integers will be able to fit in an int variable)
Output
The contents of the array followed by a newline character.