I've implemented merge sort in C/C . But my code takes longer time than the code I pulled from a website.

The recursive code seems to be exactly same for both cases:

void mergeSort(int* arr, int l, int h) {
    if (l < h) {
        int mid = (l   h) / 2;
        mergeSort(arr,l,mid);
        mergeSort(arr, mid   1, h);
        merge(arr, l, mid, h);
    }
}

However the merge algorithm is a bit different, but I don't see any significant difference here.

My merge algorithm :

void merge(int *arr, int l, int mid, int h) {
    int i = l, j = mid 1, k = l;
    int* newSorted = new int[h 1]();
    while (i <= mid && j <= h) {
        if (arr[i] < arr[j])
            newSorted[k  ] = arr[i  ];
        else
            newSorted[k  ] = arr[j  ];
    }
    for (; i <= mid; i  )
        newSorted[k  ] = arr[i];
    for (; j <= h; j  )
        newSorted[k  ] = arr[j];
    k = 0;
    for (int x = l; x <= h; x  )
        arr[x] = newSorted[x];
    delete[] newSorted;
}

Time taken for 200000 (two hundred thousand inputs) :

17 Seconds

Merge Algorithm from a website :

void merge(int arr[], int p, int q, int r) {

    int n1 = q - p   1;
    int n2 = r - q;

    int* L = new int[n1];
    int *M = new int[n2];
    

    for (int i = 0; i < n1; i  )
        L[i] = arr[p   i];
    for (int j = 0; j < n2; j  )
        M[j] = arr[q   1   j];


    int i, j, k;
    i = 0;
    j = 0;
    k = p;

    while (i < n1 && j < n2) {
        if (L[i] <= M[j]) {
            arr[k] = L[i];
            i  ;
        }
        else {
            arr[k] = M[j];
            j  ;
        }
        k  ;
    }


    while (i < n1) {
        arr[k] = L[i];
        i  ;
        k  ;
    }

    while (j < n2) {
        arr[k] = M[j];
        j  ;
        k  ;
    }
    delete[] L;
    delete[] M;
}

Time taken for 200000 (two hundred thousand inputs) :

0 Seconds

There is a massive difference in time. I don't understand the problem in my code. I would really appreciate if someone can help me figure this out. Thank you.

CodePudding user response：

Your algorithm need to allocate [h 1] for each step.

The algorithm from a website only need to allocate [r-p 1] (your h = its r, your l = its p)