MergeSort recursion explained-CodePudding

I know this question has been asked a lot and there are many useful and good answers but I have a specific question about the recursion. When we call sort recursively many times, what exactly happens? Example: int[] intArr = {16, 12, 9, 3, 19}; When we split that array into 2 parts or look at it with two indices, what does merge() do with that two unsorted parts? I mean in the first iteration the first two halfs are unsorted, right? And the method should reach merge() with this current order: merge({16, 12}, {9, 3, 19})

public static int[] sort(int l, int r) { 
     
    if (l < r) { 
        int q = (l   r) / 2; 
         
        sort(l, q); 
        sort(q   1, r); 
        merge(l, q, r); 
    } 
    return intArr; 
}

I don't know what the problem is but I don't get the recursion behind Merge Sort completely. There's a basic understanding but the merge()-method makes it difficult for me.

CodePudding user response：

When you call sort(0, 4) for intArr = {16, 12, 9, 3, 19} you will have another call to sort(0, 2), then sort(0, 1) and finally sort(0, 0). When you reach that l < r will no longer hold true and you will return the unchanged array as an array with one element 16 is already sorted. So we are back to the call to sort(0,1) so the next thing would be the call to sort(1,1) where l < r will no longer hold true and you will return the unchanged array as 12 is a single element and therefore already sorted. Only then you will reach the first merge(0, 1) call which will take {16, 12, 9, 3, 19} and sort all values from 0 to 1 so the result will be (assuming ascending order) {12, 16, 9, 3, 19}. Notice, that we call merge(0, 1) with two sorted arrays left and right from q. Then we have finished the sort(0, 1) call and move back to the previous sort(0, 2) call and now have a call to sort(2, 2). This will return the array unchanged as l < r is no longer true and we move on to merge(0, 2) with the array {12, 16, 9, 3, 19}. The result of that call will be {9, 12, 16, 3, 19} and we've finished sort(0, 2) and move to sort(0, 4) and so on.

I suggest you debug through your program (or print the indices for your sort() calls) and you will see that the first merge() call only happens after a few calls to sort() and it will only ever be called for already sorted arrays left and right from it.

Also might be worth doing it on some paper so you get the concept.

16 12 9 3 19    Sort(0, 4)
16 12 9 | 3 19  Sort(0, 2)
16 12 | 9 3 19  Sort(0, 1)
16 | 12 9 3 19  Sort(0, 0)
^sorted 
16 | 12 9 3 19  Sort(1, 1)
      ^sorted 
12 16 | 9 3 19  Merge(0, 1)
  ^sorted
12 16 | 9 3 19  Sort(2, 2)
        ^sorted
9 12 16 | 3 19  Merge(0, 2)
   ^sorted
9 12 16 | 3 19  Sort(3, 4)
9 12 16 3 | 19  Sort(3, 3)
        ^sorted
9 12 16 3 | 19  Sort(4, 4)
             ^sorted
9 12 16 | 3 19  Merge(3, 4)
           ^sorted
3 9 12 16 19    Merge(0, 4)
all sorted

CodePudding user response：

Take for granted that when sort(i, j) returns, the array is sorted in [i..j].

Now sort(l, q) returns with array[l..q] sorted and sort(q 1, r) returns with array[q 1, r] sorted. Then merge(l, q, r) interleaves the two sorted subarrays in a single one so that array[l, r] becomes sorted (merging two sorted arrays is an easy operation).

Hence, mergesort sorts bigger and bigger arrays.

Notice that when l==r, the function returns immediately, because an array of a single element is perforce sorted.