Merge Sort running into infinite loop using recursion

Question

When i try to run my code using using recursion i get stuck in an infinite loop.

this is my first time implementing divide and conquer using recursion so i am a bit rusty on the concepts. Please have a look at the code an let me know where i can correct it.

/**
 * MergeSort.c
 *
 * Ujjwal Arora
 * 
 *
 * Implements merge sort for an array
 */

#include<stdio.h>
#include<conio.h>
void merge(int array[6],int beg,int mid,int end);
void mergesort(int array[6],int beg,int end);
void display(int array[6]);

int main(void)
{
     // Initializes the array
     int array[6]={3,1,2,9,5,4};
     // Initialize the beginning and the end 
     int beg=0, end=5;
     // Implement the Merge Sort 
     mergesort(array,beg,end);
     getch();
}
void mergesort(int array[6],int beg,int end) //Calls Initial merge sort
{
      int mid;

      if(beg<end)
      {
            mid=(beg+end)/2;
            mergesort(array,beg,mid);        //Left part of the array
            mergesort(array,mid+1,end);      //Right part of the array
            merge(array,beg,mid,end);        //merge two sorted arrays
      }
 }
void merge(int array[6],int beg,int mid,int end)
{
     int temp[6]; //Declare a temp array for storing the sorted data
     //Initialize the temp array
     int k=beg;
     //initialize the pointers for two sub arrays     
     int i=beg;
     int j=mid;

     while(i<=mid && j<=end)
       {
            if(array[i] < array[j])
              {
                 temp[k]=array[i];
                 i++;                     
              }
            else
              {
                 temp[k]=array[j];
                 j++;                     
              }
                 k++;              
        }            
    //Clearing any remaining elements in the sub array
     if(i>mid) 
      {
           for(int m=j;j<=end;m++)
           {
                  temp[k]= array[m];
                  k++;                      
           }               
      }        
    else 
      {
           for(int m=i;m<=mid;m++)
           {
                  temp[k]= array[m];
                  k++;
           }
      }
    //Reassign the sorted elements to the original array
    for(k=beg;k<end;k++)     
      {
          array[k]=temp[k];                                      
      }  
 display(array);           //display array
}
void display(int array[6])
{
     for(int i=0;i<6;i++)
     {
             printf("%d ",array[i]);
     }
     printf("\n");
}

Answer 1

Your first mergesort() call results in an infinite loop. beg < end will always evaluate to true as the value is not modified. Recursively calling mergesort() creates copies of those integers. Any changes inside those functions have no effect on them. Consider removing the loop. Add a check such that the function does nothing if there's only one element to be sorted.

Now, assuming your mergesort() is fixed, let's see the merge() function. An element in your array might be ignored. For example, with beg at 0, mid at 2 and end at 5. Your loop condition implies that you want i to be from 0 to 1 and j to be from 2 to 4. The fifth element is ignored. I believe you want i to range from 0 to 2 and j to range from 3 to 5, though. All while must be fixed. (<= instead?)

Furthermore, even if conditions are fixed, please check your j value carefully. For example, if you have beg at 0, end at 1 (an array with two elements), mid is obviously 0. Your merge() will start with i at 0 and j at 0. First time the loop executes, if condition is always false because they refer to same value, so else executes and turns j into 1. Another time the loop executes, if if part executes then it's fine. But.

If else part executes, i is at 0, j turns into 2. The loop exits. Next condition checking will result in else being executed as i is equal to mid. As that part executes, the loop will run once, setting the third element of your array. It shouldn't do that at all. You're sorting two, not three. This may cause a segmentation fault if it goes over array's boundary. How about setting j at mid + 1 instead?

You incorrectly specify conditions for for loop. Comma simply ignores the first condition and only second is significant. Link the conditions with && operator instead. Better off, you only need one variable here. Just i is enough. Make sure the value doesn't just start at 0. You don't want to accidentally replace the original array with garbage values trying to merge on the right side.

The condition for display() should be i < 6 also, not i < 5. Otherwise, the last element won't be displayed. And, lastly, don't forget to make it such that it doesn't fix to six elements. You might encounter some problems trying with bigger element count.

Good luck with your code!

Answer 2

when I compiled and executed your program, it terminated normally (i.e., it didn't get stuck in an infinite loop/recursion). however, it did not appear to be sorting the array correctly. I think your merging process is the problem.

if (array[i] < array[j])
{
    temp[k]=array[i];
    i++;                     
}
else
{
    temp[k]=array[j];
    j++;                     
}

giving your variables meaningless names (e.g., i, j, k, etc) makes your code much more difficult do understand. now here's a question: can i (aka beg) be ever equal to j (aka mid)? what happens in this case?

here is some pseudocode that may help you implement the merging process in a more elegant way:

define leftIndex and set it to the starting index of the left half
define rightIndex and set it to the starting index of the right half

calculate the number of elements in the two halves (in terms of the starting and ending indexes)
store the value above in SIZE
create a temporary array of size SIZE

for tempIndex = 0 to SIZE, increment tempIndex
    if leftIndex passed the ending index of the left half
        set temp[tempIndex] to array[rightIndex++]
    else if rightIndex passed the ending index of the right half
        set temp[tempIndex] to array[leftIndex++]
    else if array[leftIndex] < array[rightIndex]
        set temp[tempIndex] to array[leftIndex++]
    else
        set temp[tempIndex] to array[rightIndex++]