What's wrong with this merge sort code I have done from the CLRS?

Question

Wrong output! I have tried each and every condition but failed to get the real result

I tried to accomplish this from the clrs book pseudo-code but I failed. I am trying to write merge sort using iterators to implement myself pseudo-code in c language, but for some reason, this code is compiling but the outcome is not sorted. Can someone figure out what is wrong with it? it seems perfectly fine to my untrained eyes.

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

int a[] = {5,3,65,6,7,3,7,8};

void print_array(int a[], int size)
{
    int i;
    for(i = 0;i < size;i++)
    {
        printf("%d ",a[i]);
    }
}
void merge(int a[],int p,int q,int r)
{
    int n1,n2,i,j,k;
    n1 = q - p + 1;
    n2 = r - q;
    int l[n1];
    int m[n2];
    for(i = 0; i < n1; i++)
        l[i] = a[i+p];
    for(j = 0; j < n2; j++)
        m[j] = a[q+1+j];
    l[n1] = 9999999;
    m[n2] = 9999999;
    i = 0;
    j = 0;
    for(k = p;k < r; k++)
    {
        if(l[i] <= m[j])
        {
            a[k] = l[i];
            i = i+1;
        }
        else
        {
            a[k] = m[j];
            j = j+1;
        }
    }
}
void merge_sort(int a[],int p,int r)
{
    if(p < r)
    {
        int q = floor((p + r) / 2);
        merge_sort(a,p,q);
        merge_sort(a,q+1,r);
        merge(a,p,q,r);
    }
}
int main()
{
    int size = (sizeof(a) / sizeof(a[0]));
    print_array(a,size);
    printf("\n");
    merge_sort(a,0,size);
    print_array(a,size);
    return 0;
}

//for this input out put is showing
//-1 -1 3 3 3 -1 6 7

Answer 1

Please pay attention to array bounds and sizes:

• Your parameter r is not the size of the array, but the index of the rightmost element, so you should call merge_sort(a, 0, size - 1);.

• When you want to use a large sentinel value, after the actual array, you must allocate space for it, so:

  int l[n1];
  int m[n2];
  

• Because your value r is the index of the last element, you must consider it when merging and your loop condition should be for(k = p; k <= r; k++).

• (Not really a problem, but you don't need to use floor like in JavaScript. When a and b are integers, a / b will perform a division that results in an integer.)

In C, arrays (and ranges in general) have inclusive lower bounds and exclusive upper bounds: lo is the first valid index and hi is the first invalid index after the valid range. For array indices, lo and hi are zero and the array size.

Embrace this convention. The C indices lead to the following style:

• The length of a range is hi - lo;
• Forward loops are for (i = lo; i < hi; i++);
• Adjacent ranges share the hi and lo values.

For example, in your merge function the middle value p would be the first value in the right range, but also the exclusive upper bound of the left range.

If pseudocode or code in other languages uses one-based indices, I recommend translating it to the zero-based, exclusive upper-bound style of C. After a while, you'll get suspicious of spurious - 1's and <='s. :)