Recursion is like a loop, but different.
A loop iterates until an end condition;
recursion 'calls itself' until a base case.
Loops iterate like a story from beginning to end;
recursion is like a story where each chapter is enclosed in the previous chapter... until you get to the innermost chapter (the base case). Only after reading this innermost chapter can you finally understand clearly what is happening. So now you can back up one chapter and re-read it, and understand that chapter. As you go on understanding and backing-up the hierarchy of chapters, you finally reach the start of the story and have finished (understanding) the book.
In this example, the base case is array.length < 2
: an array with one or zero elements. Any array of one/zero elements is by definition already sorted.
After breaking the array down like this, we ask: "what small work can I contribute to ensure — as we recombine the array — that it will be recombined in a sorted order?" In this example that work is the merge
function.
mergeSort
divides the array-argument and calls itself until the array has been completely divided into one-element arrays. It calls itself here:
return merge( mergeSort(leftSide), mergeSort(rightSide))
This line of code is added to the call stack, but to evaluate merge
, mergeSort
must be evaluated first. So mergeSort
is added to the call stack, and run. But each time it runs, there is another return of merge()
. This results in the call stack piling up with calls to merge
. We cannot begin to go back up the call stack and evaluate merge()
until we stop calling it: when the base case is finally met. Now we begin to 'back out of our story', starting with the innermost chapter, and going back up the call stack.
As we go back up the stack, we contribute work in the form of the merge function: We compare the first elements of the leftSide
and rightSide
and sort them. Whichever side
is less than the other gets pushed
into the result
and that side
gets shifted
(replaced) by the next element.
Why does this work?
This algorithm ensures that even if the smallest element is initially last (or the biggest element is first), they will be sorted, even though the work done is only comparing two characters each step. By breaking down the array (and piling up the call stack) in this way, we ensure that merge will always be called enough times, so that the smallest number will always 'get to the front of the queue' at each step, and there will be 'enough steps' that it will come out first.
In the GeekForGeeks image of Mohammed's answer, check the path of the number 3. It is 'worked on' by the merge function 3 times. Each time it 'gets to the front of the queue': the first time the queue is only of two (elements in length), the second time the queue is of 4 and the third time the queue is of 7 (or 8). Even if 3 had been initially last (and the example array had been a length of 8) it would still only have been 'worked on' three times and would still have got to the front of the queue. You may realise that for any array of length upto 2n that n steps of work (comparisons) are needed on the smallest element (or by extension: on each element ) to bring it to the front of the queue (or by extension: the sorted position ), no matter where it starts in the array.
[5]
and[3, 8]
are sorted, thereturn merge...
line callsmerge
with[5]
and[3, 8]
, which returns[3, 5, 8]
. Something similar happens in the right half:[10]
is returned,[4, 1]
is sorted to[1, 4]
and then[10]
and[1, 4]
are merged into[1, 4, 10]
. Finally[3, 5, 8]
and[1, 4, 10]
is merged into[1, 3, 4, 5, 8, 10]
. Each recursive call keeps its own copy of the local variables along the way.[5, 3, 8, 10, 4, 1]
, that gets split inmergeSort
into two arrays. Both those arrays are (recursively) passed intomergeSort
again, where[5, 3, 8]
becomes[5]
and[3, 8]
. For[5]
we're done, and it gets returned as is. For[3,8]
, we again recurse, and they end up returend as[3]
and[8]
. Those getmerge
d: what happens during the merge step? Write it out: it's an important exercise if you want to understand any algorithm.