Почему мой код на mergesort не работает

---

#include<stdlib.h>
#include<stdio.h>
#include<iostream>
#include<math.h>
using namespace std;
void InsertSort(int *A,int n){
    for(int p=1;p-1<n;p++)
    {
        int key=A[p-1];//It used to compare
        while(key>A[p]){
            int temp=A[p];
            A[p]=A[p-1];
            A[p-1]=temp;
            for(int i=p-1;A[i]<A[i-1];i--){
                int temp=A[i];
                A[i]=A[i-1];
                A[i-1]=temp;
            }
        }
    }
}
void Merge(int* A,int left,int mid,int right){
    int i,j,k;
    int n1=mid-left+1;
    int n2=right-mid;
    //create the temprorte array
    int* L=(int*)malloc(n1*sizeof(int));
    int* R=(int*)malloc(n2*sizeof(int));
    //use a loop to merge
    for(i=0;i<n1;i++){
        L[i]=A[left+i];
    }
    for(j=0;j<n2;j++){
        R[j]=A[mid+1+j];
    }
    /* Merge the temp arrays back into arr[l..r] */
    i = 0; // Initial index of first subarray
    j = 0; // Initial index of second subarray
    k = left; // Initial index of merged subarray
    for (; i < n1 && j < n2; k++) {
        if (L[i] <= R[j]) {
            A[k] = L[i];
            i++;
        } else {
            A[k] = R[j];
            j++;
        }
    }
    /* Copy the remaining elements of L[], if there
    are any */
    for(; i < n1; i++, k++){
        A[k] = L[i];
    }
    /* Copy the remaining elements of R[], if there
    are any */
    for(; j < n2; j++, k++){
        A[k] = R[j];
    }

    free(L);
    free(R);
} 
void MergeSort(int* A,int left,int right){
    if(right<left){
    // when the size of the subarray is two, stop dividing
        int mid=left+(right-left)/2;
        MergeSort(A,left,mid);
        MergeSort(A,mid+1,right);
        Merge(A, left, mid, right);
    }
}
int main(){
    int* arrIS;//array for insertion sort
    int* arrME;//array for merge sort;
    int n1=10,n2=pow(10,5);
    //n1=10 TEST
    arrIS=(int*)malloc(n1*sizeof(int));
    arrME=(int*)malloc(n1*sizeof(int));

    //assign values to both arrays
    srand(time(NULL));//Should only be called once
    for(int i=0;i<n1;i++){
        int r=rand()%10;
        arrIS[i]=r;
        arrME[i]=r;
    }
    //print out the result
    //This is for the insertsort method
    for(int i=0;i<n1;i++){
        cout<<arrIS[i]<<" ";
    }cout<<endl;
    InsertSort(arrIS,n1);
    for(int i=0;i<n1;i++){
        cout<<arrIS[i]<<" ";
    }cout<<endl;
    //This is for the mergesort method
    for(int i=0;i<n1;i++){
        cout<<arrME[i]<<" ";
    }cout<<endl;
    MergeSort(arrME,0,n1-1);
    for(int i=0;i<n1;i++){
        cout<<arrME[i]<<" ";
    }cout<<endl;
}

Что я уже пробовал:

У меня есть это:
7 1 0 9 1 5 9 4 7 3
0 1 1 3 4 5 7 7 9 9
7 1 0 9 1 5 9 4 7 3
7 1 0 9 1 5 9 4 7 3


Результат метода MergeSort должен быть таким же, как и метод InsertSort.Я не понимаю, почему это не работает.

---