Time limit: 5000ms
Memory limit: 256mb

Description:
In this exercise, you are required to complete the function MergeSort() and merge() which sorts some integers (not necessarily distinct) in descending order. You can find the pseudocode in lecture notes. (ch6.pptx)

1. Print the sorted array in descending order.
2. Sort the array in descending order.

You can assume that all the integers of A[] after sorting may not distinct, which means that A[0] >= A[1] >= … >= A[n-1].

The code template has been provided. Your task is to complete the following functions.

void void merge(int A[], int left, int mid, int right, int n)
Example:
You have an array A: [1,2,6,1,5,7] whose left part [1,2,6] and right part [1,5,7] are sorted, then this function is called to merge these two parts together. 
The result array should be [7,6,5,2,1,1]

void MergeSort(int A[], int left, int right, int n)
Example:
You have an array A before sorting: [1,2,6,5,1,7], then this function is called to sort A[left]...A[right] in descending order. 
The result array should be [7,6,5,2,1,1]

You could declare some variables yourself in the functions. However, you are not allowed to use any addtional array to do the partition.

Sample Input 1:
10
2 1 4 10 3 5 7 8 9 6

Sample Output 1:
10 9 8 7 6 5 4 3 2 1 

Sample Input 2:
5
1 2 1 2 1

Sample Output 2:
2 2 1 1 1 

Code Template:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void PrintArray(int A[], int n)
{
    for(int i=0; i < n; i++)
        printf("%d ", A[i]);
    printf("\n");
}

void merge(int A[], int left, int mid, int right, int n){
    /*
        Fill in your code here.
    */
}

void MergeSort(int A[], int left, int right, int n)
{
    /*
        Fill in your code here.
    */
}

int main()
{
    int n;
    scanf("%d",&n);

    int A[n];

    for(int i=0; i < n; i++) scanf("%d", &A[i]);
        
    MergeSort(A, 0, n-1, n);
    PrintArray(A, n);
    return 0;
}