I have written a code of mergeSort(from clrs book) but not getting an output

user_8776586 0
Viewed 117

I have taken a reference from clrs book of Introduction to Algorithms of Merge Sort Algorithms and written a program in C language. Though I had check it manually by pen and paper the code seems to be correct then also I am not getting the right output.

The Output is shown below:

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

void merge(int array[], int start, int middle, int end) {
    int n1 = middle - start + 1;
    int n2 = end - start;
    int i;
    int leftarray[n1 + 1], rightarray[n2 + 1];
    for (i = 0; i < n1; i++) {
        leftarray[i] = array[start + i];
    }
    for (int j = 0; i < n2; i++) {
        rightarray[j] = array[middle + j + 1];
    }
    leftarray[n1 + 1] = 1000000;
    rightarray[n2 + 1] = 1000000;
    
    int k, j = 0;
    i = 0;
    for (k = start; k <= end; k++) {
        if (leftarray[i] > rightarray[j]) {
            array[k] = rightarray[j];
            j++;
        } else {
            array[k] = leftarray[i];
            i++;
        }
    }
}

void mergeSort(int array[], int start, int end) {
    if (start < end) {
        int middle = (start + end) / 2;
        mergeSort(array, start, middle);
        mergeSort(array, middle + 1, end);
        merge(array, start, middle, end);   
    }
}

void sorting(int array[], int length) {
    int i;
    for (i = 0; i < length; i++) {
        printf("%d ", array[i]);
    }   
}

int main() {
    int noOfelements;
    scanf("%d", &noOfelements);
    int array[noOfelements];
    for (int i = 0; i < noOfelements; i++) {
        scanf("%d", &array[i]);
    }
    printf("Before Sorting: ");
    sorting(array, noOfelements);
    mergeSort(array, 0, noOfelements - 1);
    printf("After Sorting: ");
    sorting(array, noOfelements);
    return 0;   
}

Output of the Above Program:

5
5 4 3 2 1 
Before Sorting: 5 4 3 2 1 After Sorting: 2 0 5 0 32
mergesort c algorithm
1 Answers

Although the book Introduction to Algorithms by Thomas H Cormen, Charles E Leiserson , Ronald L Rivest, and Clifford Stein, is considered an excellent textbook, the algorithm you implemented has several shortcomings:

  • it uses the concept of sentinel values, values set at the end of the arrays to be merged, supposedly larger than any existing values, to hopefully simplify the merging process. In reality, there are no such values as if there were any, why should they not appear in the arrays as regular values?
  • it uses end as the index of the last element in the array: it would be much simpler to use end as the index of the first element beyond the array, thus removing the need for confusing +1 / -1 adjustments and allowing for empty arrays.
  • you use int middle = (start + end) / 2; which could overflow for large values of start and end, although other parts of your implementation would fail if you try and sort such a huge array. Still it is safer to write int middle = start + (end - start) / 2;

Your code fails because you set the sentinel values one position too far. You should write:

  leftarray[n1] = 1000000;
  rightarray[n2] = 1000000;

Here is a better approach:

#include <stdio.h>

void merge(int array[], int start, int middle, int end) {
    int n1 = middle - start;
    int i, j, k;

    // save the elements from the left half, no need to save the right half
    int leftarray[n1];
    for (i = 0; i < n1; i++) {
        leftarray[i] = array[start + i];
    }
    
    for (i = 0, j = middle, k = start; i < n1; k++) {
        if (j >= end || leftarray[i] <= array[j]) {
            array[k] = leftarray[i];
            i++;
        } else {
            array[k] = array[j];
            j++;
        }
    }
}

void mergeSort(int array[], int start, int end) {
    if (end - start >= 2) {
        int middle = start + (end - start) / 2;
        if (middle - start > 100000) {
            // avoid stack overflow: allocate at most 100k ints for `leftarray`
            middle = start + 100000;
        }
        mergeSort(array, start, middle);
        mergeSort(array, middle, end);
        merge(array, start, middle, end);   
    }
}

void print_array(const char *prefix, const int array[], int length) {
    printf("%s:", prefix);
    for (int i = 0; i < length; i++) {
        printf(" %d", array[i]);
    }
    printf("\n");
}

int main() {
    int noOfelements;
    if (scanf("%d", &noOfelements) != 1 || noOfelements < 0)
        return 1;
    int array[noOfelements];
    for (int i = 0; i < noOfelements; i++) {
        if (scanf("%d", &array[i]) != 1)
            return 1;
    }
    print_array("Before Sorting", array, noOfelements);
    mergeSort(array, 0, noOfelements);
    print_array("After Sorting", array, noOfelements);
    return 0;   
}
user_45932670
Related