Merge Sort Base Case

user_4699255 0
Viewed 286

I'm practicing sorting algorithms and I'm stuck on this silly issue.

hackerearth

I specifically don't understand how the array is partitioned to arrays that only contain single (sorted) element. I drew out a call stack example to illustrate my confusion.

void merge_sort(int A[], int start, int end) {
    if (start < end) {
        int mid = (start + end ) / 2;
        merge_sort(A, start, mid);                 
        merge_sort(A, mid + 1, end);
        merge(A, start, mid, end);   
    }                    
}

the call stack should look something like this

merge_sort(A,0,5) A [9,7,8,3,2,1]

merge_sort(A,0,2) A [9,7,8]

merge_sort(A,0,1) A [9,7]

merge_sort(A,0,0) -> here the base case would fail, no?

in which case the array would not get partitioned into singleton arrays.

mergesort sorting c++
3 Answers

When start == end it means there's only a single element to "sort".

And since start == end also means that start < end will be false, then from that follows that the function skips everything inside the if body.

So merge_sort(A,0,0) doesn't do anything, but return back up the call-stack to merge_sort(A,0,1) .

Looking at the merge_sort(A, 0, 1) call specifically it looks like this:

merge_sort(A, 0, 1)
    merge_sort(A, 0, 0)  // Does nothing
    merge_sort(A, 1, 1)  // Does nothing
    merge(A, 0, 0, 1)    // Merge the two partition 0-0 with 1-1

So once merge_sort(A, 0, 0) returns (without doing anything) then merge_sort(A, 1, 1) is called which again does nothing but return. Anmd then the two sub-arrays are "merged" with merge(A, 0, 0, 1).

user_4405580

The recursive call to merge_sort(A,0,0) returns immediately because left == right ie: a slice with a single element.

user_45932670

Base case would return cause start == end and not start < end

user_117317570
Related