Merge Sort Base Case (Recursion) Dissect

Question

From the book Robert Sedgewick & Kevin Wayne Algorithms 4th Edition In recursion part base case code is ``` if(end <= start) { return; } ``` But I've checked `end` never become lower than the `start` index. only `end = start` happen when there's only 1 element left. Then why `<=` less than operator is used where only one condition that is equal `=` works all the time? Suppose an array `a[8,5,3]` is taken. Now the middle point is 1st index so after divide ``` a[8,5] and a[3] ``` `divide(a,0,1) and divide(a,2,2), merge(a,0,1,2)` start is smaller than end in `divide(a,0,1)` and `start=end` happen in `divide(a,2,2)` function call. Now mid is 0th index. ``` a[8] and a[5] ``` `divide(a,0,0) and divide(a,1,1), merge(a,0,0,1)` here in both function call `start=end` is only true. so literally `end` never became smaller than `start` thus `end<start` never happen. only `end=start` happen. can anyone explain me why do we use the < (less than) operator in base case of merge sort? Full Recursive Co…

Accepted Answer

It is correct that the `divide` function never calls itself with arguments so that `end < start`. So therefore the if-statement could just as well be `if (end == start)`.

Maybe it's to catch if the divide function is called from another piece of code in an incorrect way, e.g.

```
void foo(int a[]) 
{ 
    divide(a, 5, 3);
}
```

That would cause an infinit loop if your check only was `==` instead of `<=`. Therefor it seems more safe to use `<=`.

The original code could also be rewritten like:

```
int divide(int a[], int start, int end)
{
    int mid;

if(end > start)
    {
        mid = (start+end)/2;
        divide(a, start, mid);
        divide(a, mid+1, end);
        merge(a, start, mid, end);
    }
}
```

In any case it probably doesn't matter for performance - an optimizing compiler will re-arrange things anyway.

BTW: Notice that your function is said to return an int but you don't do that. Maybe you really want it to be: void divide(.....)

Merge Sort Base Case (Recursion) Dissect

Solution

Problem