Writing Merge Sort Pseudo-Code Procedure in C

Question

I have been going through Introduction to Algorithms, and have been trying to implement the MERGE-SORT algorithm in C programming language to gain a better understanding of it.

The book presents two pseudo-codes:

and

While I do understand the above procedures, I must be missing something during the implementation.

I must be missing something from the pseudo-code but cannot figure it out yet. Any suggestions as to why this is happening would be appreciated.

EDIT: Updated Code and Output

/* C program for Merge Sort */
#include<stdlib.h>
#include<stdio.h>

void MERGE(int [], int , int , int );
void printArray(int [], int );
void MERGE_SORT(int [], int , int );

int main(void)
{
   int A[] = { 12, 11, 13, 5, 6, 7, 2, 9 };
   int arr_size = sizeof(A) / sizeof(A[0]);

   printf("Given array is \n");
   printArray(A, arr_size);

   MERGE_SORT(A, 0, arr_size); //Fixed: Index to start from zero

   printf("\nSorted array is \n");
   printArray(A, arr_size);

   return 0;
}

void MERGE(int A[], int p, int q, int r)
{
   int i = 0;
   int j = 0;
   int n1 = q - p + 1;                  //Computing length of sub-array 1
   int n2 = r - q;                      //Computing length of sub-array 2
   int *L = malloc((n1 + 2) * sizeof(*L + 1));        //Creating Left array
   int *R = malloc((n2 + 2) * sizeof(*R + 1));        //Creating Right array

   for (int i = 0; i <= n1; i++) { //Fixed: <=, i start from 0
       L[i] = A[p + i - 1];
   }
   for (int j = 0; j <= n2; j++) { //Fixed: <=, i start from 0
       R[j] = A[q + j];
   }

   L[n1 + 1] = 99;  //Placing Sentinel at the end of array
   R[n2 + 1] = 99;

   i = 1;
   j = 1;

   /*Prior to the first iteration k = p, so the subarray is empty.
   Both L[i] and R[j] are the smallest elements of their arrays and have not
   been copied back to A*/
   for (int k = p; k <= r; k++) { //Fixed: <=
       if (L[i] <= R[j]) {
           A[k] = L[i];
           i++;
       }
       else { //Fixed: Assignment and not condition check for A[k]
           A[k] = R[j];
           j++;
       }
   }

   free(L);
   free(R);
}

void MERGE_SORT(int A[], int p, int r)
{
   //During first iteration p = 1 & r = 8
   if (p < r) {
       int q = (p + r) / 2;
       MERGE_SORT(A, p, q);
       MERGE_SORT(A, q + 1, r);
       MERGE(A, p, q, r);
   }
}

/* Function to print an array */
void printArray(int Arr[], int size)
{
   int i;
   for (i = 0; i < size; i++)
       printf("%d ", Arr[i]);
   printf("\n");
}

If you look carefully at the pseudocode, you'd notice that you should have `L[n1+1] = 99;` and `R[n2+1] = 99;`. Not `L[n1] = 99;` and `R[n2] = 99;` — Dima Chubarov, Mar 18 '18 at 09:37
@DmitriChubarov, I was trying that, however it results in a `Heap Corruption Detected`, meaning that I am writing into unallocated memory, damaging the data structures used to make the memory allocator work. The pseudo-code is written in a 1-Indexed Array notation. — rrz0, Mar 18 '18 at 09:39
@DmitriChubarov, since in line 3 there is written "Let `L[1..n1 +1]`", this is the same as `L[0..n1]`. Thus later I am writing the sentinel value to `L[n1]`. Please correct me if I am doing something wrong. — rrz0, Mar 18 '18 at 09:44
You are correct, you have to carefully change indices from 1-based to 0-based throughout the code — Dima Chubarov, Mar 18 '18 at 09:54
Your function declarations at the beginning of the code are all wrong. You are supposed to use *types* of the arguments, not names (or types and names together just like in the definitions). — n. m. could be an AI, Mar 18 '18 at 10:00
In the pseudocode, array indices are imclusive, so `let A[m,n] be array` means A has n-m+1 elements indexed from m to n inclusively. In C, `int A[m]` has m elements indexed from 0 to m-1 inclusively. You need to account for that. — n. m. could be an AI, Mar 18 '18 at 10:07
@n.m. thanks for your helpful comments. Regarding the function declarations, that is something I will address immediately. Bad mistake from my end. — rrz0, Mar 18 '18 at 10:11

Sunil Chaudhary · Accepted Answer · 2018-03-18T10:50:10.260

Looked in the pseudo code and found out that some things have been mistakenly written wrong.
1. You need to be careful with the array index to start from 0 or 1
2. Merge last part in for loop is actually an assignment instead for conditional check.

Edit: Have updated the code to fix for the error Stack around the variable A was corrupted

Please find the corrected code here(Lookout for //Fixed for fixes)

/* C program for Merge Sort */
#include<stdlib.h>
#include<stdio.h>

void MERGE(A, p, q, r);
void printArray(Arr, size);
void MERGE_SORT(A, p, r);

int main(void)
{
   int A[] = { 12, 11, 13, 5, 6, 7, 2, 9 };
   int arr_size = sizeof(A) / sizeof(A[0]);

   printf("Given array is \n");
   printArray(A, arr_size);

   MERGE_SORT(A, 0, arr_size - 1); //Fixed: Index to start from zero, arr_size - 1

   printf("\nSorted array is \n");
   printArray(A, arr_size);

   return 0;
}

void MERGE(int A[], int p, int q, int r)
{
   int i = 0;
   int j = 0;
   int n1 = q - p + 1;                  //Computing length of sub-array 1
   int n2 = r - q;                      //Computing length of sub-array 2
   int *L = malloc((n1+1) * sizeof(*L+1));          //Creating Left array
   int *R = malloc((n2+1) * sizeof(*R+1));          //Creating Right array
   for (int i = 0; i < n1; i++) { //Fixed: i start from 0
       L[i] = A[p + i];

   }
   // int arr_size = sizeof(A) / sizeof(A[0]);
   for (int j = 0; j < n2; j++) { //Fixed: j start from 0
       R[j] = A[q + j + 1];

   }

   L[n1] = 99;  //Placing Sentinel at the end of array
   R[n2] = 99;

   i = 0; //Fixed: i and j to start from 0
   j = 0;

   /*Prior to the first iteration k = p, so the subarray is empty.
   Both L[i] and R[j] are the smallest elements of their arrays and have not
   been copied back to A*/
   for (int k = p; k <= r; k++) { //Fixed: <=
       if (L[i] <= R[j]) {
           A[k] = L[i];
           i++;
       }
       else { //Fixed: Assignment and not condition check for A[k]
        A[k] = R[j];
        j++;
       }
   }

   free(L);
   free(R);
}

void MERGE_SORT(int A[], int p, int r)
{
   //During first iteration p = 1 & r = 8
   if (p < r) {
       int q = (p + r) / 2;
       MERGE_SORT(A, p, q);
       MERGE_SORT(A, q + 1, r);
       MERGE(A, p, q, r);
   }
}

/* Function to print an array */
void printArray(int Arr[], int size)
{
   int i;
   for (i = 0; i < size; i++)
       printf("%d ", Arr[i]);
   printf("\n", size);
}

Hope it helps.
Revert for any doubts.

Many thanks for the helpful answer. I see many instances where I have gone wrong. For some reason with the above alterations I get a `Run-time Check Failure #2` - `Stack around variable 'A' was corrupted.` I will try to look further into this. — rrz0, Mar 18 '18 at 10:09
I have updated the code. At some places in the code, I was trying to get the value from array A which didn't exist. I was trying to access A[A.length + 1] which was causing the errors. — Sunil Chaudhary, Mar 18 '18 at 10:48
Yes, that was it. I particularly missed that `i` and `j` should have been initialized to 0! Thanks for your help. — rrz0, Mar 18 '18 at 10:55

score 1 · Answer 2 · edited Mar 18 '18 at 12:59

here are some changes i have done to your code `

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

void MERGE(int *A,int p,int q,int r);
void printArray(int *Arr,int size);
void MERGE_SORT(int *A,int p,int r);

int main(void){
    int A[] = { 12, 11, 13, 5, 6, 7, 2, 9 };
    int arr_size = sizeof(A) / sizeof(A[0]);

    printf("Given array is \n");
    printArray(A, arr_size);

    MERGE_SORT(A, 0, arr_size -1); // pass the indices of the array

    printf("\nSorted array is \n");
    printArray(A, arr_size);

    return 0;
}

void MERGE(int A[], int p, int q, int r){
    int i = 0;
    int j = 0;
    int k; //declair it here
    int n1 = q - p + 1;                //Computing length of sub-array 1
    int n2 = r - q;                    //Computing length of sub-array 2
    int *L = malloc((n1) * sizeof(*L+1));          //Creating Left array
    int *R = malloc((n2) * sizeof(*R+1));       //Creating Right array

    for (int i = 0; i < n1; i++) { //start coping from zero
        L[i] = A[p + i];
   }
   for (int j = 0; j < n2; j++) {
        R[j] = A[q +1 + j];
   }

  // L[n1] = 99;  we won't be needing these as to mark the end we already know the size of arrays
  // R[n2] = 99;

  // i = 1;
  // j = 1;

   /*Prior to the first iteration k = p, so the subarray is empty.
   Both L[i] and R[j] are the smallest elements of their arrays and have not
   been copied back to A*/
    for (k = p; k < r+1 && i < n1 && j<n2; k++) { 
    //i & j checks weather the array has completed or not
        if (L[i] <= R[j]) {
            A[k] = L[i];
            i++;
       }
       else {
           A[k]=R[j];
           j++;
        }
   }
// when one of the array is empty u can copy the rest of the array with out compairing
  while(i<n1)
      A[k++]=L[i++];
  while(j<n2)
      A[k++]=R[j++];


   free(L);
   free(R);
}

void MERGE_SORT(int A[], int p, int r)
{
   //During first iteration p = 1 & r = 8
   if (p < r) {
       int q = (p + r) / 2;
       MERGE_SORT(A, p, q);
       MERGE_SORT(A, q + 1, r);
       MERGE(A, p, q, r);
    }
}

/* Function to print an array */
void printArray(int Arr[], int size){
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", Arr[i]);
        printf("\n");
}`

first of all you were not passing the right parameters to the function. then the concept of using infinity to indicate is not good as one can want to sort bigger number than that in that case you would have to increase infinity an alternative approach is given above. Mean while i also solved the problem with your code here it was again with the array index were not rightly used check it out now its working:`

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

void MERGE(A, p, q, r);
void printArray(Arr, size);
void MERGE_SORT(A, p, r);

int main(void)
{
    int A[] = { 12, 11, 13, 5, 6, 7, 2, 9 };
    int arr_size = sizeof(A) / sizeof(A[0]);

    printf("Given array is \n");
    printArray(A, arr_size);

    MERGE_SORT(A, 1, arr_size);

    printf("\nSorted array is \n");
    printArray(A, arr_size);

    return 0;
}

void MERGE(int A[], int p, int q, int r)
{
    int i = 0;
    int j = 0;
    int n1 = q - p + 1;                //Computing length of sub-array 1
    int n2 = r - q;                    //Computing length of sub-array 2
    int *L = malloc((n1+1) * sizeof(*L+1));       //Creating Left array
   int *R = malloc((n2+1) * sizeof(*R+1));       //Creating Right array

   for (int i = 1; i < n1; i++) {
       L[i] = A[p + i - 1];
   }
   for (int j = 1; j < n2; j++) {
       R[j] = A[q + j];
   }

   L[n1] = 99;  //Placing Sentinel at the end of array
   R[n2] = 99;

   i = 1;
   j = 1;

   /*Prior to the first iteration k = p, so the subarray is empty.
   Both L[i] and R[j] are the smallest elements of their arrays and have not
   been copied back to A*/
   for (int k = p; k < r; k++) {
       if (L[i] <= R[j]) {
           A[k] = L[i];
           i++;
       }
       else if (A[k] == L[i])
           j++;
   }

   free(L);
   free(R);
}

void MERGE_SORT(int A[], int p, int r)
{
   //During first iteration p = 1 & r = 8
   if (p < r) {
       int q = (p + r) / 2;
       MERGE_SORT(A, p, q);
       MERGE_SORT(A, q + 1, r);
       MERGE(A, p, q, r);
   }
}

/* Function to print an array */

void printArray(int Arr[], int size)
{
   int i;
   for (i = 0; i < size; i++)
       printf("%d ", Arr[i]);

   printf("\n");
}

Thanks for your help! I have noted some changes and will try them soon. — rrz0, Mar 18 '18 at 11:26

Writing Merge Sort Pseudo-Code Procedure in C

2 Answers2

Linked