Merge sort

[cppnoob25]

Can anyone explain how this code works? Conceptually I understand merge sort but I found this code and I have some questions on it.

void merge(int a[], int startIndex, int endIndex)
{

int size = (endIndex - startIndex) + 1;
int *b = new int [size]();

int i = startIndex;
int mid = (startIndex + endIndex)/2;
int k = 0;
int j = mid + 1;

while (k < size)
{
    if((i<=mid) && (a[i] < a[j]))
    {
        b[k++] = a[i++];
    }
    else
    {
        b[k++] = a[j++];
    }

}

for(k=0; k < size; k++)
{
    a[startIndex+k] = b[k];
}

delete []b;

}

//The recursive merge sort function
void merge_sort(int iArray[], int startIndex, int endIndex)
{
int midIndex;

//Check for base case
if (startIndex >= endIndex)
{
    return;
}

//First, divide in half
midIndex = (startIndex + endIndex)/2;

//First recursive call
merge_sort(iArray, startIndex, midIndex);
//Second recursive call
merge_sort(iArray, midIndex+1, endIndex);
//The merge function
merge(iArray, startIndex, endIndex);

}

//The main function
int main(int argc, char *argv[])
{
int iArray[10] = {2,5,6,4,7,2,8,3,9,10};

merge_sort(iArray, 0, 9);

//Print the sorted array
for(int i=0; i < 10; i++)
{
    cout << iArray[i] << " ";
}

return 0;
}

When the recursive calls are being called in the merge sort function. How doesn't the program go into an infinite loop there? That's really the only part I'm confused about.

How does it ever skip over this call

merge_sort(iArray, startIndex, midIndex);

and go into this call

merge_sort(iArray, midIndex+1, endIndex);

[ne555]

debugger, set a breakpoint in merge_sort, watch the parameters, continue the recursive calls, watch how the function returns at line 42

[cppnoob25]

okay, so I see how it's working now. It returns at line 42 and then goes to line 52. What exactly happens when return is run after finishing with line 49 for it's final run. I'm still a little blank when it comes to recursion.

[cppnoob25]

can anyone else explain the mergesort function? Maybe visually?

[Duthomhas]

I really need to fix the FAQ to be much easier to read for this stuff...

Imagine you have two stacks of plates with numbers on them. It doesn't matter what numbers, just that they are in two stacks, and that each stack is already sorted.

Now to merge the stacks, take the smallest of the two top plates and set it in a new stack. Repeat until there are no more plates to merge. Your final stack of plates is sorted.

The trick is in finding the "already sorted" stacks in your array.
There are many ways to do that. The code you have above does it by simply dividing the array in half and then doing another merge sort on each half. Once the two halves have been merge-sorted, you can merge them together to make your final, completely-sorted array.

Hope this helps.