归并排序

#include <iostream>

using namespace std;

void MergeSort(int *a, int left, int right);
void Merge(int *a, int left, int mid, int right);
void output(int n, int *a);

int main()
{
    int n;
    int *a;
    cin >> n;
    a = (int *)malloc(n * sizeof(int));
    for (int i = 0; i < n;i++)
    {
        cin >> a[i];
    }
    MergeSort(a, 0, n - 1);
    output(n, a);
}

void input(int *n,int **a)
{

}

void MergeSort(int *a,int left,int right)
{
    if(left<right)
    {
        int mid = (left + right) / 2;
        MergeSort(a, left, mid);
        MergeSort(a, mid + 1, right);
        Merge(a, left, mid, right);
    }
}

void Merge(int *a,int left,int mid,int right)
{
    int i = left;
    int j = mid + 1;
    int k = 0;
    int *tmp = (int *)malloc((right - left + 1) * sizeof(int));
    while(i<=mid&&j<=right)
    {
        if(a[i]<=a[j])
        {
            tmp[k++] = a[i++];
        }
        
        else
        {
            tmp[k++] = a[j++];
        }
        
    }

    while(i<=mid)
    {
        tmp[k++] = a[i++];
    }

    while(j<=right)
    {
        tmp[k++] = a[j++];
    }

    for(k=0 ,i=left;i<=right;i++,k++)
    {
        a[i] = tmp[k];
    }
}

void output(int n,int *a)
{
    for (int i = 0; i < n;i++)
    {
        cout << a[i] << endl;
    }
}