How to implement merge sort from “The Introduction

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

Here is my attempt. Known bugs: since INT_MAX is used as a sentinel, sorting an array containing INT_MAX may cause the pointers to overflow during the merge.

#include <stdio.h>
#include <limits.h>
void merge(int A[], unsigned int p, unsigned int q, unsigned int r){
    unsigned int n1 = q - p; //differs from book because C indexes from 0
    unsigned int n2 = r - q;


    int L[n1 + 1]; // L contains the first elem of A, up to the midpoint (not including the midpoint)
    int R[n2 + 1]; // R contains the elems including the midpoint of A all the way to the end.

    L[n1] = INT_MAX; //INT_MAX is our sentinel, which will be used in the merge step. No possible int will be greater than INT_MAX, so during the merge,
    R[n2] = INT_MAX; // INT_MAX is similar to the infinity used in the book

    for (unsigned int i = 0; i < n1; i++){
        L[i] = A[p + i];
    }

    for (unsigned int i = 0; i < n2; i++){
        R[i] = A[q + i];
    }
    // Now we just need to merge L and R and sort A
    // The sorting occurs here, during the merge.
    unsigned int i = 0;
    unsigned int j = 0;

    for (unsigned int k = p; k < r; k++){
        if (L[i] <= R[j]){
            A[k] = L[i];
            i++;
        }
        else{
            A[k] = R[j];
            j++;
        }
    }
}
void merge_sort(int A[], unsigned int p, unsigned int r) { // input is array A, first elem p, and last elem + 1 r

    if (p < r - 1) { //differs from book... since C indexes from 0, if we have an array of size 1, we will subtract 1 to get 0 and then hit the base case

        // Otherwise, find the midpoint and divide and conquer
        unsigned int q = (p + r) / 2; //q is the midpoint of A
        merge_sort(A, p, q); //this must process the midpoint
        merge_sort(A, q, r); //this must process the elem after the midpoint to the last elem
        merge(A, p, q, r);
        return;


    }

}


int main(){

    int A[] = {432, 5, 99, 101, 43};
    unsigned int len_A = sizeof(A)/sizeof(A[0]);

    printf("original order of elems in A: \n");

    for (unsigned int i = 0; i < len_A; i++){
        printf("%d ", A[i]);
    }

    merge_sort(A, 0, len_A);

    printf("\n\n");
    printf("after performing merge_sort: \n");


    for (unsigned int i = 0; i < len_A; i++){
        printf("%d ", A[i]);
    }

    printf("\n\n");

return 0;
}

Answer 3

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;

            }           
        }
    }
}

Answer 4

This one worked for me

    // MergeSortRevisionAgain.cpp : Defines the entry point for the console application.
//Understanding merge sort
#include <iostream>

using std::cout;
using std::endl;


//The declaration of the merge sort function
void merge(int A[], int p, int q, int r);
int* mergeSort(int A[], int p, int r);


int main()
{

    /*My Code to test for the merge sort*/
    int myArray[]{ 2,3,5,7,1,4,7,9};
    int lengthOfArray = sizeof(myArray) / sizeof(myArray[1]);
    int* sortedOutput = mergeSort(myArray, 0, lengthOfArray-1);

    for (int i = 0; i <lengthOfArray; i++)
    {
        cout << sortedOutput[i] << " ";
    }

    cout << endl;


    return 0;
}


void merge(int A[], int p, int q, int r)
{
    //Declaration of number of variable in each half
    int n1 = q - p + 1;                                                             //1. n1 = q - p + 1
    int n2 = r - q;                                                                 //2. n2 = r-q

    //Declaration of left and right part of the array
    int* leftArray= new int[n1+1] ;                                                 //3. Let L[1...n1+1] and ... 
    int* rightArray= new int[n2+1] ;                                                //... R[1...n2+1] be new arrays

    //Entering the for loop for the left side
    for (int i = 0; i < n1; i++)                                                    //4.for i = 1 to n1 NB(change i to 0 since index in c++ starts from 0)
    {
        leftArray[i] = A[p + i ];                                                   //5. L[i] = A[p+i-1] NB(change to A[p+i] since "i" was changed to 0 hence A[p,...,p+i)
    }

    //Entering the for loop for the right side
    for (int  j = 0; j < n2; j++)                                                   //6. for j = 1 to n2 NB(change j j= 0 since index in c++ starts from 0)
    {
        rightArray[j] = A[q + j+1];                                                 //7. R[i] = A[q + j ] NB(change to A[q+j+1] since "j" was changed to 0  hence A[q+1,...q+1+j]
    }

    leftArray[n1] = 999;                                                            //8. Set L[n1+1] = sentinel NB last value in leftArray will be the sentinel
    rightArray[n2] = 999;                                                           //9. Set L[n2 + 2] = sentinel NB last value in rightArray will be the sentinel

    int i = 0;                                                                      //10. i = 1 change to i = 0 since index starts from 0 in c++
    int j = 0;                                                                      //11. j = 1 change to j = 0 since index starts from 0 in c++

    for (int k = p; k <= r; k++)                                                    //12. for k = p to r - change as specified in code since index of array p = 0, r = lengthofArray - 1
    {
        if (leftArray[i] <= rightArray[j])                                          //13. L[i] <= R[j]
        {
            A[k] = leftArray[i];                                                    //14. A[k] = L[i]
            i = i + 1;                                                              //15. i = i + 1
        }
        else
        {
            A[k] = rightArray[j];                                                   //16. A[k] = R[j]
            j = j + 1;                                                              //17. j = j+1;
        }
    }

    delete leftArray;                                                               //18. Free allocated dynamic memory for leftArray
    leftArray = nullptr;                                                            //19. Set pointer to nullptr to prevent access to deleted memory
    delete rightArray;                                                              //20. Free allocated dynamic memory for rightArray              
    rightArray = nullptr;                                                           //21. Set pointer to nullptr to prevent access to deleted memory
}

int* mergeSort(int A[], int p, int r)
{
    if (p < r)
    {
        int q = floor((p + r) / 2);
        mergeSort(A, p, q );
        mergeSort(A, q + 1, r);
        merge(A, p, q, r);
    }

    return A;
}