3

I have been going through Introduction to Algorithms and am trying to implement the pseudo-code presented for merge-sort using C programming language.

This is the pseudo-code presented for the MERGE procedure:

enter image description here

While I understand this procedure, I am struggling to implement in C when arriving at the 3rd line. My compiler is giving an error (and rightly so after C99) expression must have a constant value.

Error is occurring on line 3 of the pseudo-code or at int L[n1]; in code posted below

How can I create an array which holds n1 and n2 values which are constantly changing from one iteration to the next? Any suggestions would be appreciated.

I also came across https://www.geeksforgeeks.org/merge-sort/ to see how it might be done, and the website is using the same syntax as I am, but without any compiler warnings. Is this because of an older compiler version (C99?) or am I missing something from my end?

My code is below:

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

#define infinite 9999;      //Used for sentinels

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]);

   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[n1];               //Creating Left array
   int R[n2];               //Creating Right array

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

   L[n1] = 99;  //Placing Ssentinel 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++;
   }

}

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);
   }
}

EDIT

Code for MERGE updated as follows thanks to suggestions from answer and comments below. Even though the code below presents no syntax or run-time errors, the output is still not correct. This is out of the scope of the question, however. Another question was asked here: Writing Merge Sort Pseudo-Code Procedure in C

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

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

   L[n1] = 99;  //<-- Some modification must be carried out here to allocate 
   R[n2] = 99;  //`99` to the end of array

   i = 1;
   j = 1;

   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);  //Freeing both pointers at the end of iteration
}
4
  • You don't mention which line is the error happening at. Commented Mar 18, 2018 at 8:21
  • Error was at the 3rd line. Mentioned in my question but it may not have been clear. Will edit. Commented Mar 18, 2018 at 8:23
  • 1
    You probably want else if (A[k] == L[i]) instead of else if (A[k] = L[i]). If your compiler does not issue a warning about this you need to enable (more) warnings. Commented Mar 18, 2018 at 9:07
  • Just saw that there are no warnings. You are absolutely correct. I am using Visual Studio 2017 and might need to alter some settings from within. Commented Mar 18, 2018 at 9:10

1 Answer 1

3

To create an array with size computed at runtime, use malloc()

int *L = malloc(n1 * sizeof(*L));
if (L == NULL) {
    // handle error
}

The code you linked to is using Variable Length Arrays which is supported by some but not all C compilers. See :

Passing array to a function (and why it does not work in C++)

This is accessing past the end of the array

L[n1] = 99;  //<-- Some modification must be carried out here to allocate 
R[n2] = 99;  //`99` to the end of array

Remember, with an array containing n elements, valid indices are 0 - n-1

Sign up to request clarification or add additional context in comments.

13 Comments

Thanks for your answer, this helps! Does one need to proceed by: free(ptr); and ptr = NULL; in this case or is it not necessary?
Use free after you are done working with the memory.
Once you have copied all elements of your subarrays back to the original array is a good time to free the subarrays. In this case, it looks like that would be at the very end of MERGE().
Note that ptr = NULL is not needed, it's just a good habit to avoid dangling pointers.
Yep, that's perfectly fine...just make sure you get your parentheses correct
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.