c - Why my 'mergesort' fails at large # of numbers?

Question

I have a code of mergesort, it works well with N=68,000 or less, but when the # of numbers increase to 70,000, there's error that some of the elements are not sorted. My friend guess it's because I used too many malloc, but I don't know why.

keytype is just an "unsigned long" type defined by myself. A is a pre-set array by keytype* A = (keytype *)malloc(N * sizeof(keytype)); and filled by random numbers.

typedef unsigned long keytype;
keytype *new_part(int start, int end, keytype* A) {
    int N = end - start + 1;
    keytype* cc = (keytype *)malloc(N * sizeof(keytype));
    for (int i = 0; i < N; i++) {
        cc[i] = A[start + i];
    }
    return cc;
}
void mySort(int N, keytype* A){
    if (N == 1) return;
    int mid = N / 2;
    keytype* first = new_part(0, mid - 1, A);
    keytype* second = new_part(mid, N - 1, A);
    mySort(mid, first);
    mySort(N - mid, second);
    int a = 0, b = 0;
    for (int i = 0; i < N; i++) {
        if (a >= mid) {
            A[i] = second[b];
            b++;
            continue;
        }
        if (b >= N - mid) {
            A[i] = first[a];
            a++;
            continue;
        }
        if (first[a]>second[b]) {
            A[i] = second[b];
            b++;
            continue;
        }
        if (first[a] < second[b]) {
            A[i] = first[a];
            a++;
            continue;
        }
    }
    free(first);
    free(second);
}

标签： c