# Merge Sort running into infinite loop using recursion

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");
}
``````
• hi, @Ujjwal Arora! your question may have a better chance of getting answered if you format your code according to the style guidelines. see manual.cs50.net/style!
– kzidane
Mar 27 '16 at 13:15
• @Kareem: Thank You for your suggestions,i have reformatted the code to make it presentable,please have a look. Mar 27 '16 at 14:51
• Are you running your code on the IDE and does it compile? If so, what is the purpose of the getch line in main? Could it be that the blinking cursor you're seeing is not an infinite loop but the program waiting for an input when it executes that line? Finally, in your mergesort function, you want mid=(beg+end)/2 inside the while loop for it to be recursive, otherwise its value will never change. Mar 28 '16 at 12:16
• Hi @ronga ,i included the getch as i wanted to see the output if it was being executed correctly. Also,could you please elaborate on the mid=(beg+end)/2 being included inside the while loop? i am new to recursion and my implementation is a bit scratchy.My IDE is Dev C++ Mar 28 '16 at 13:54
• Ok, so that answers the compilation issue, I can't seem to compile it on my end using the terminal, and I'm guessing neither can check50, so unless it can run on CS50 IDE, it won't pass. As Aquablitz below correctly identified (and which I inadvertently failed to mention), end, beg and mid are all staying static and not updating. For them to update, you need to put them within the while loop, so their values change each time the loop executes. As it is, their values are fixed as initial values you pass to the function. Also, your using a "," to separate conditions in the for loop should be ok. Mar 29 '16 at 3:54

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!

• Thank You @AquaBlitz11,I have made the necessary changes in the code,i am afraid i am still hazy on our explanation on variable "j". "Furthermore, please check your j value carefully. For example, if you have beg at 0, end at 1 and mid at 0, your i and j will be the same and your loops are prone to copying same value twice.". Could you please explain the same in a little detail? I have also modified my code to incorporate the logic pitfalls but my program is crashing,could you please take a look? Mar 29 '16 at 21:23
• Okay, I added an explanation on that part. That should also explain possible segmentation fault. And, it seems like you forgot to change your last `for` loop condition in `merge()`. It should be `i <= end`. Mar 30 '16 at 7:32

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++]
``````