1

A merge sorting algorithm is not working as it is supposed to do. The output values are not fully sorted in the ascending order. Some of the values are out of order which is pointing to a bug.

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

void merge(int *L, int *R, int *a, int nL, int nR) {
    int i, j, k;
    i = j = k = 0;

    while ((i < nL) && (j < nL)) {
        if (L[i] < R[j]) {
            a[k] = L[i];
            ++i;
        } else {
            a[k] = R[j];
            ++j;
        }
        ++k;
    }

    while (i < nL) {
        a[k] = L[i];
        ++i;
        ++k;
    }

    while (j < nR) {
        a[k] = R[j];
        ++j;
        ++k;
    }
}

void mergeSort(int *a, int n) {
    if (n < 2)
        return;

    int i, mid, *L, *R;

    mid = n / 2;

    L = (int *)malloc(mid * sizeof(int));
    R = (int *)malloc((n - mid) * sizeof(int));

    for (i = 0; i < mid; ++i) {
        L[i] = a[i];
    }

    for (i = mid; i < n; ++i) {
        R[i - mid] = a[i];
    }

    mergeSort(L, mid);
    mergeSort(R, n - mid);

    merge(L, R, a, mid, n - mid);

    free(L);
    free(R);
}

int main() {
    int i, n, *a;

    scanf("%d", &n);

    a = (int *)malloc(n * sizeof(int));

    for (i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }

    mergeSort(a, n);

    for (i = 0; i < n; ++i) {
        printf("%d ", a[i]);
    }

    free(a);

    return 0;
}

For example, for the following inputs: 10 10 9 8 7 6 5 4 3 2 1

I should get these outputs: 1 2 3 4 5 6 7 8 9 10

But the outputs are not in the ascending order. The outputs are:1 3 4 5 2 6 8 9 10 7

2
  • the mergesort algorithm does not involve any calls to malloc() nor free() Suggest reading: mergesort algorithm Commented Aug 19, 2020 at 16:19
  • regarding: I should get these outputs: 1 2 3 4 5 6 7 8 9 10 The mergesort algorithm does NOT remove duplicates, so the output should be: 1 2 3 4 5 6 7 8 9 10 10 Commented Aug 19, 2020 at 16:24

1 Answer 1

4

Not sure if it covers all the problems but

while((i < nL) && (j < nL))

should be

while((i < nL) && (j < nR))
                        ^
                        note
Sign up to request clarification or add additional context in comments.

2 Comments

Just looking is not enough. You need to debug, trace through, try various use cases. You need to split your code in pieces and put in back together.
Thanks for your suggestion

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.