Merge sort algorithm in C not working as expected

Question

I am trying to implement the merge sort algorithm in C. I understand how the algorithm is supposed to work however I am encountering some difficulties with the implementation.

I understand that there are hundreds of examples and source code for it's implementation but I was hoping someone could help me understand why mine is not working correctly.

My code is below and after the code I explain what I have tried so far.

#include <stdio.h>

void merge(int a[], int L[], int R[],int nL, int nR) //nL and nR are the lengths of L[] and R[]
{
   int i = 0 , j = 0, k = 0;

    while(i<nL && j <nR)
    {
        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)    //n is the length of a[]
{
   if(n < 2) return;     //BASE CASE
   int mid = n / 2;

   int left[mid];
   int right[n-mid];

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

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

   int nL = sizeof(left) / sizeof(left[0]);
   int nR = sizeof(right) / sizeof(right[0]);

   mergesort(left, nL);
   mergesort(right, nR);
   merge(a,left,right,nL,nR); 
}    


int main(void)
{
    printf("Initial:\n");
    printf("3 4 1 6\n");

    int numbers[4] = {3,4,1,6};
    int n = sizeof(numbers) / sizeof(int);

    mergesort(numbers,n);
    printf("Sorted:\n");
    for(int i =0 ; i < 4; i++)
    {
        printf("%d ", numbers[i]);
    }

    return 0;
}

As it is and with the unsorted array [3,4,1,6] the output is 0 0 1 3. Clearly the 1 and 3 are in the right order relative to each other but the two zeros at the beginning are clearly wrong. At first it seemed to me that I was inserting 4 and 6 to the right and out of bounds of the array.

I used some print statements to try and debug but I haven't been able to figure out what was going on. I even tried to follow my code with gdb but I still could not sort it.

Does any one have any ideas of what might be happening?

When you ran it in the debugger, which was the first line whose behaviour diverged from what you were anticipating? — Oliver Charlesworth
– Oliver Charlesworth, Commented Sep 23, 2013 at 23:26
Not that this is the problem, but you don't need the sizeof() calculations. You already know the length of each subsequence : mid and n-mid. What is more likely the problem, assuming your merge() algorithm is correct (a big assumption) your right-side copy isn't correct. It should run to i < n , not i < n-1. — WhozCraig
– WhozCraig, Commented Sep 23, 2013 at 23:28
Agree with WhozCraig that the -1 in for(int i = mid; i < n-1; i++) is unwanted. For the rest, debug by providing yourself with a function void dump_array(const char *tag, int n, int *a) { printf("%d:", n); for (int i = 0; i < n; i++) printf("%s:%d:", a[i]); putchar('\n'); } and call it frequently: on entry to mergesort() (dump_array("enter", n, a);), after you've created the left array, after you've created the right array, after you've merge sorted the left array, after you've merge sorted the right array, after you've merged the result. It will help you narrow down the problems. — Jonathan Leffler
– Jonathan Leffler, Commented Sep 23, 2013 at 23:41
I can't support Jonathan's comment enough. When working on partitioning sorting algorithms like mergesort, quicksort, etc. a debug routine that dumps a suspect sequence for you is near-mandatory to help check yourself during development. — WhozCraig
– WhozCraig, Commented Sep 23, 2013 at 23:43
Waah: typos in my code — and they're only editable for 5 minutes. Provide yourself with a function void dump_array(const char *tag, int n, int *a) { printf("%s:%d:", tag, n); for (int i = 0; i < n; i++) printf(" %3d", a[i]); putchar('\n'); } and call it frequently: on entry to mergesort() (for example, dump_array("-->>mergesort()", n, a);), after creating the left array, after creating the right array, after merge sorting the left array, after merge sorting the right array, after merging the result (dump_array("<<--mergesort()", n, a);). It will help you narrow down the problems. — Jonathan Leffler
– Jonathan Leffler, Commented Sep 23, 2013 at 23:56

Jonathan Leffler · Accepted Answer · 2013-09-24 05:01:28Z

3

A more nearly idiomatic way of writing the merge() code would be:

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

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

That's about half the number of lines of your code, and within broad limits, the less code there is to read, the better. There are those who insist on having braces after each loop or conditional. I don't think that's necessary (or particularly helpful), but if that's the style you like, you can use it.

Your mergesort() code is less flabby, but could be changed to:

void mergesort(int a[],int n)    //n is the length of a[]
{
    if (n < 2)
        return;     //BASE CASE
    int mid = n / 2;
    int left[mid];
    int right[n-mid];

    for (int i = 0; i < mid; i++)
        left[i] = a[i];

    for (int i = mid; i < n; i++)
        right[i-mid] = a[i];

    mergesort(left, mid);
    mergesort(right, n - mid);
    merge(a, left, right, mid, n - mid); 
}

This includes the fix for your main problem — the loop loading the right array was leaving the last element uncopied.

With a debugging function such as:

void dump_array(const char *tag, int n, int *a)
{
    printf("%s:%d:", tag, n);
    for (int i = 0; i < n; i++)
        printf(" %3d", a[i]);
    putchar('\n');
}

You can do a lot of effective debugging with:

void mergesort(int a[],int n)
{
    if (n < 2)
        return;
    int mid = n / 2;
    int left[mid];
    int right[n-mid];

    dump_array("-->>mergesort()", n, a);

    for (int i = 0; i < mid; i++)
        left[i] = a[i];
    dump_array("left", mid, left);

    for (int i = mid; i < n; i++)
        right[i-mid] = a[i];
    dump_array("right", n - mid, right);

    mergesort(left, mid);
    dump_array("merged-L", mid, left);
    mergesort(right, n - mid);
    dump_array("merged-R", n - mid, right);
    merge(a, left, right, mid, n - mid);
    dump_array("<<--mergesort()", n, a);
}

In your code, the output with the tag right would show 0 or semi-random data for the last element, rather than what you're expecting. This would be a hint as to where the trouble is. Keep the dump_array() function around; it is a useful creature to have. It's a simple-minded version; you can invent more complex versions which outputs a newline at intermediate positions for long arrays, for example.

answered Sep 24, 2013 at 5:01

Jonathan Leffler

760k145 gold badges961 silver badges1.3k bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

WhozCraig Over a year ago

+1 a very concise and easy to understand merge(). I'm impressed the OP actually used a mergesort algorithm that used an array and element count for input rather than what most instructors seem to try and shovel them; an array and bookend indices. And if I could +1 this again for the generic "show-me-da-buffer" function I would.

raed Over a year ago

Sorry it took a while to accept the answer. Thank you very much for all the insight into the mergesort and how I can better write it. And I will definitely take note and use that dump_array function.

user1952500 · Accepted Answer · 2013-09-24 03:05:14Z

2

The issue is in the following code:

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

It should be:

   for(int i = mid; i < n; i++) // right should range from mid to n - 1 *inclusive*
   {
        right[i-mid] = a[i];
   }

answered Sep 24, 2013 at 3:05

user1952500

6,7915 gold badges29 silver badges40 bronze badges

Comments

Jonathan Leffler · Accepted Answer · 2019-09-03 17:01:16Z

0

This is simple implementation of merge sort without any complications. Just pass the array pointer and total number of entires in the array.

void merge(int *a, int top)// Array pointer and max entries
{
    int l1, k, l2, u1, u2, size = 1, i, j;
    int *sa;
    sa = (int *)calloc(top, sizeof(int));

    while (size < top)
    {
        l1 = 0;
        k = 0;
        while (l1 + size < top)
        {
            l2 = l1 + size;
            u1 = l2 - 1;
            u2 = ((l2 + size - 1) < top ? l2 + size - 1 : top - 1);

            for (i = l1, j = l2; i <= u1 && j <= u2; )// Merging
            {
                sa[k++] = a[i] <= a[j] ? a[i++] : a[j++];
            }
            for ( ; i <= u1; )
                sa[k++] = a[i++];
            for ( ; j <= u2; )
                sa[k++] = a[j++];
            l1 = u2 + 1;
        }

        for (i = l1; i < top; i++) // For the left outs of the process
            sa[k++] = a[i];

        for (i = 0; i < top; i++)
            a[i] = sa[i];

        size *= 2;
    }
}

edited Sep 3, 2019 at 17:01

Jonathan Leffler

760k145 gold badges961 silver badges1.3k bronze badges

answered Nov 8, 2013 at 20:37

Bug Killer

497 bronze badges

3 Comments

Jonathan Leffler Over a year ago

This code has a major memory leak — sa is allocated but neither returned nor freed.

Jonathan Leffler Over a year ago

Also, a for loop with no initialization or reinitialization clause (such as for ( ; i <= u1; )) is a while loop and should be written while (i <= u1).

Jonathan Leffler Over a year ago

However, with the memory leak fixed (free(sa); just before returning), the code does work. (It sorts even without that fix; it can be used more often with the fix.) It doesn't explain what is wrong with the original code in the question, though. It avoids recursion, replacing it with iteration. It allocates as much space as the recursive versions do, but does the allocation with a single calloc() (though malloc() would be better/adequate; the array elements are initialized before they're used). It can handle bigger arrays because it is not constrained by the size of the stack.

Collectives™ on Stack Overflow

Merge sort algorithm in C not working as expected

3 Answers 3

2 Comments

Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related