How to implement merge sort from "The Introduction to Algorithms" by Cormen and Co

Question

I'm learning algorithms from Cormen and Co. and I have problem with implementation of merge sort from their pseudocode. I compiled it by:

$ gcc -Wall -g merge_sort.c

I have a problem because for numbers:

2 4 5 7 1 2 3 6

The result is:

1 2 2 3 3 4 5 5 

I tried to read carefully the pseudo code but this does not help me. I want to know what I'm doing wrong. Below is my code:

#include <stdio.h>

#define SIZE 8

void merge(int *array_of_integers, int p, int q, int r) {
    int n1 = q - p + 1;
    int n2 = r - q; 
    int i, j, k;
    int left_array[n1 + 1];
    int right_array[n2 + 1];

    for (i = 0; i < n1; i++)
        left_array[i] = array_of_integers[p + i];
    for (j = 0; j < n2; j++)
        right_array[j] = array_of_integers[q + j];

    i = 0;
    j = 0;

    for (k = p; k < r; k++){
        if (left_array[i] <= right_array[j]) {
            array_of_integers[k] = left_array[i];
            i++;
        } else {
            array_of_integers[k] = right_array[j];
            j++;
        }   
    }
}

void merge_sort(int *array_of_integers, int p, int r) {
    if (p < r) {
        int q = (p + r) / 2;
        merge_sort(array_of_integers, p, q);
        merge_sort(array_of_integers, q + 1, r);
        merge(array_of_integers, p, q, r);
    }
}

void print_array(int *array_of_integers, int amout_of_integers) {
    int i;
    for(i = 0; i < amout_of_integers; i++)
        printf("%d ", array_of_integers[i]);
    puts("");
}

int main(void) {
    int dataset[] = { 2, 4, 5, 7, 1, 2, 3, 6 };

    print_array(dataset, SIZE);
    merge_sort(dataset, 0, SIZE);
    print_array(dataset, SIZE);

    return 0;
}

Edit: (Correct solution)

 void merge(int *array_of_integers, int p, int q, int r) {
     int n1 = q - p + 1;
     int n2 = r - q; 
     int i, j, k;
     int left_array[n1 + 1];
     int right_array[n2 + 1];

     left_array[n1] = 123456798;
     right_array[n2] = 123456798;

     for (i = 0; i < n1; i++)
         left_array[i] = array_of_integers[p + i];
     for (j = 0; j < n2; j++)
         right_array[j] = array_of_integers[q + j + 1];

     i = 0;
     j = 0;

     for (k = p; k <= r; k++) {
         if (left_array[i] <= right_array[j]) {
             array_of_integers[k] = left_array[i];
             i++;
         } else {
             array_of_integers[k] = right_array[j];
             j++;
         }
     }
 }

 void merge_sort(int *array_of_integers, int p, int r) {
     if(p < r) {
         int q = (p + r) / 2;
         merge_sort(array_of_integers, p, q);
         merge_sort(array_of_integers, q + 1, r);
         merge(array_of_integers, p, q, r);
     }
 }

Answer 1

There are two problems in your code.

One, you need to clarify what the parameters you are passing mean. Inside merge_sort, it looks like p is the first element to be sorted, and r is the last element to be sorted. But, where merge_sort is called, in main, it is passed 0 and SIZE. Here, 0 is the first element to be sorted, but SIZE cannot be the last element, because it is (presumably) the number of elements to be sorted. In your example, you are passing 8, but the last element to be sorted is 7. So decide whether you want to change merge_sort so that r is the number of elements or whether you want to change main to pass SIZE-1. Similarly, in merge, p seems to be the first element to merge, q is the last element of the first range (so q+1 is the first of the second), and r is the last element of the second range. But when you copy from array_of_integers to right_array, you copy from q+j. When j is zero, this copies the last element of the first range, but you want the first element of the second range. So you need to clear up these uses of the indices. (Also, you only need n1 and n2 elements for left_array and right_array, not n1+1 and n2+1.) Also check the loop on k, for(k = p; k < r; k++). What should the continuation condition on that loop be?

Two, when you merge left_array and right_array, you do not account for the fact that an array might be empty (because all elements have been copied out of it previously), so comparing left_array[i] to right_array[j] does not work because i or j is indicating an element outside of the left_array or of the right_array, respectively. For example, if i has reached its limit (n1), then you should not compare. Instead, you should just take an element from right_array.

Answer 2

this one works though its implemented in Java, the logic is the same obviously . I have taken care of all the points suggested in the answer by Eric. Please check out the code, it's self explanatory.

import java.util.*;
class MergeSort
{

    public static void main(String args[])
    {
        int testArray[] = {1,3,5,3,1,7,8,9};
        mergeSort(testArray,0,testArray.length-1);
        System.out.println(Arrays.toString(testArray));
    }

    protected static void mergeSort(int arr[], int p, int r)
    {
        int q;
        if (p<r)
        {
            q = (p+r)/2;
            mergeSort(arr,p,q);
            mergeSort(arr, q+1, r);
            merge(arr,p,q,r);   
        }   
    }

    protected static void merge(int arr[], int p, int q, int r)
    {    
        int n = q-p+1;
        int m = r-q;

        int L[] = new int[n+1];
        int R[] = new int[m+1];
        int i,j,k;

        for(i=0; i< n; i++)
        {
            L[i] = arr[p+i];    
        }
        for(j=0; j< m; j++)
        {
            R[j] = arr[q+j+1];    
        }

        L[n] = Integer.MAX_VALUE;
        R[m] = Integer.MAX_VALUE;

        i = 0;
        j = 0;
        for(k = p; k<= r; k++)
        {

            if( L[i]<=R[j])
            {
                arr[k] = L[i];
                i = i+1;
            }
            else
            {
                arr[k] = R[j];
                j = j+1;

            }           
        }
    }
}