Description
HA! You activated my trap card! Now you must sort my cards using the merge sort algorithm.
Merge Sorting is an essential way to sort arrays. The algorithm is a 'divide and conquer' algorithm. In other words, 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)
For this problem, you must write the mergesort function is already provided, so you only need to code the following function:
void merge(int*, int, int, int);
Now sort these cards or else you will be sent to the shadow realm.
Input
the first line contains the integer N (1 <= N <= 5000)
The following N lines contain the integers to be sorted. (1 <= num <= 5000)
Output
The process of the sorting (already provided by the partial judge) and the final value of the sorting.