Infinite recursive call in Objective-C

Question

I am working on the implementation of merge-sort in Objective-C (code below) I am having hard time understanding why my recursive call is an infinite loop when I don't increment variable 'middle' by one.

So [self sort:array fromLow:middle+1 toHigh:high]; works fine

but [self sort:array fromLow:middle toHigh:high]; turns my program into an infinite loop. Can anyone explain me why it's happening? In both cases the if statement

 if(high<=low)
    {
        return;
    }

is reached and executed, so I would think that my program will move on to the 3rd statement (mergeLow: andHigh: andMiddle: inArray: andHelperArray:) but it doesn't.

Sort Method:

-(void)sort:(NSMutableArray *)array fromLow:(unsigned long)low toHigh:(unsigned long) high{


    if(high<=low) //recursive condition fullfilled
    {
        return;
    }
    unsigned long middle = low + (high - low)/2; //calculating middle element

    [self sort:array fromLow:low toHigh:middle]; //(1)sort left

    [self sort:array fromLow:middle+1 toHigh:high];//(2)sort right

    [self mergeLow:low andHigh:high andMiddle:middle inArray:array andHelperArray:[array mutableCopy]];//(3) merge left and right 

}

Debugging I tried to debug it. To do it I commented out call (3) to the merge method and added nslog statement logging values of high and low variables.

 MergeSort *is = [MergeSort new];
 NSArray * a1 = @[@10,@9,@22,@5];
 [is sort:a1.mutableCopy fromLow:0 toHigh:a1.count];

Updated Sorting Method

-(void)sort:(NSMutableArray *)array fromLow:(unsigned long)low toHigh:(unsigned long) high{
    //recursive condition fullfilled

    NSLog(@"High: %lu Low %lu ",high, low);
    if(high<=low)
    {

        return;
    }
    unsigned long middle = low + (high - low)/2;

    [self sort:array fromLow:low toHigh:middle];

    [self sort:array fromLow:middle + 1 toHigh:high];

  // [self mergeLow:low andHigh:high andMiddle:middle inArray:array andHelperArray:[array mutableCopy]];

}

Debugging Output: middle+1

2013-10-28 11:37:21.484 Algorithms[52598:303] High: 4 Low 0 
2013-10-28 11:37:21.486 Algorithms[52598:303] High: 2 Low 0 
2013-10-28 11:37:21.486 Algorithms[52598:303] High: 1 Low 0 
2013-10-28 11:37:21.487 Algorithms[52598:303] High: 0 Low 0 
2013-10-28 11:37:21.487 Algorithms[52598:303] High: 1 Low 1 
2013-10-28 11:37:21.488 Algorithms[52598:303] High: 2 Low 2 
2013-10-28 11:37:21.488 Algorithms[52598:303] High: 4 Low 3 
2013-10-28 11:37:21.488 Algorithms[52598:303] High: 3 Low 3 
2013-10-28 11:37:21.489 Algorithms[52598:303] High: 4 Low 4 

Now in the same method I am executing the [self sort:array fromLow:middle toHigh:high]; without incrementing the middle variable and getting the following output:

Debugging Output: middle

2013-10-28 11:45:55.689 Algorithms[52674:303] High: 4 Low 0 
2013-10-28 11:45:55.691 Algorithms[52674:303] High: 2 Low 0 
2013-10-28 11:45:55.691 Algorithms[52674:303] High: 1 Low 0 
2013-10-28 11:45:55.692 Algorithms[52674:303] High: 0 Low 0 
2013-10-28 11:45:55.692 Algorithms[52674:303] High: 1 Low 0 
2013-10-28 11:45:55.693 Algorithms[52674:303] High: 0 Low 0 
2013-10-28 11:45:55.693 Algorithms[52674:303] High: 1 Low 0 
2013-10-28 11:45:55.693 Algorithms[52674:303] High: 0 Low 0 
2013-10-28 11:45:55.694 Algorithms[52674:303] High: 1 Low 0 
2013-10-28 11:45:55.694 Algorithms[52674:303] High: 0 Low 0 
2013-10-28 11:45:55.694 Algorithms[52674:303] High: 1 Low 0 
2013-10-28 11:45:55.695 Algorithms[52674:303] High: 0 Low 0 
2013-10-28 11:45:55.695 Algorithms[52674:303] High: 1 Low 0 
2013-10-28 11:45:55.696 Algorithms[52674:303] High: 0 Low 0 
2013-10-28 11:45:55.696 Algorithms[52674:303] High: 1 Low 0 
2013-10-28 11:45:55.696 Algorithms[52674:303] High: 0 Low 0 
2013-10-28 11:45:55.697 Algorithms[52674:303] High: 1 Low 0 
2013-10-28 11:45:55.697 Algorithms[52674:303] High: 0 Low 0 
2013-10-28 11:45:55.698 Algorithms[52674:303] High: 1 Low 0 
2013-10-28 11:45:55.698 Algorithms[52674:303] High: 0 Low 0 
2013-10-28 11:45:55.699 Algorithms[52674:303] High: 1 Low 0 
2013-10-28 11:45:55.699 Algorithms[52674:303] High: 0 Low 0 
2013-10-28 11:45:55.699 Algorithms[52674:303] High: 1 Low 0 
2013-10-28 11:45:55.700 Algorithms[52674:303] High: 0 Low 0 
2013-10-28 11:45:55.700 Algorithms[52674:303] High: 1 Low 0 
2013-10-28 11:45:55.700 Algorithms[52674:303] High: 0 Low 0 
2013-10-28 11:45:55.701 Algorithms[52674:303] High: 1 Low 0 
2013-10-28 11:45:55.701 Algorithms[52674:303] High: 0 Low 0 
2013-10-28 11:45:55.702 Algorithms[52674:303] High: 1 Low 0 
2013-10-28 11:45:55.702 Algorithms[52674:303] High: 0 Low 0 
2013-10-28 11:45:55.702 Algorithms[52674:303] High: 1 Low 0 

Answer 1

You are including the middle element in both calls ('left' and 'right').

In the case you just have 2 elements, so 0 and 1, you get middle element to be 0.5 which is 0 as int, and you define 'left' as being [0], and 'right' as being [0,1], so 'right' ends up being what you had in the beginning.

That is why if you define 'righ't as starting on middle + 1 you don't get that. Because 'left' will go up to middle, and 'right' will start right after. They won't have anything in common.

EDIT (Some more info):

One concept you should always have in mind when using recursive algorithms is that termination can only be guaranteed if every time you do a call to the recursive function you have somehow reduced the problem to some simpler instance than it was before.

What is usually done is that you define some kind of measure that you can relate to each call of the recursive function, and then you prove that each call reduces this measure. If you know that at the termination condition this measure should have a certain value, you are now sure that the problem will eventually be reduced to the termination condition and end.

In this case, what you can use as measure would be the size of the arrays you're ordering. You must guarantee that each call to the recursive function will take a smaller array than what it was called with. You failed this when the right part of the array would end up being called with the same size as the original.