3

I dont want to put too much code so I'll just put the code that involves recursion. This algorithm is fairly well known so I think everybody knows the basic code.

void mergeSort(int array[], int l, int r) 
{
    if (l < r) 
    {
        int m = l + (r - l) / 2;
        mergeSort(array,l,m);
        mergeSort(array,m+1,r);

        merge(array,l,m,r);
    }
}

where the merge function is the typical function which compares two sets and organises them.

Now, I only understand the recursion here by "brute force". With this I mean that I have to actually compute each step along the way to see that it works. But I'm completely 100% sure it would never had occurred to me to code things up this way.

I was hoping that someone could provide me with insight as to how I should think about these two recursion calls, and how its obvious it had to be this way. I know this might seem broad, but I was hoping anyone could provide me with insight so that I shouldn't have to use the "brute force" approach I mentioned above. Perhaps you could tell me how you think about these recursive calls (i dont think you compute each step like me since that is extremely tedious).

  • In some sense, most fundamental computer algorithms require proofs, in the same way that mathematical theorems require proofs. Programmers may not spend time looking up and understand the proofs of things we use, but this is a matter of laziness, just like we don't look up dictionary words very often. If the issue of correctness comes up, it is better to look for some reliable references. – rwong Jul 12 '16 at 14:09
  • Are you familar with proofs by induction in math? – RemcoGerlich Jul 12 '16 at 14:30
  • @RemcoGerlich Yes. Why? – DLV Jul 12 '16 at 17:28
  • @rwong are you implying a regular programmer doesn't fully understand this code? Even though I myself don't completely dominate it, I would think it is a fairly easy algorithm for an experienced programmer. – DLV Jul 12 '16 at 17:31
  • You can think of it as like a reduce operation – Elliot Gorokhovsky Jul 12 '16 at 23:27
5

The recursive MergeSort is a "divide and conquer" algorithm. The code you provided in your example basically does this (in plain English):

  1. Find the middle point
  2. Sort the left half,
  3. Sort the right half.
  4. Merge the two halves back together.

The key to understanding how this works recursively is that, when it goes to sort the left half, it divides that into two parts again, just like it did with the first two halves, and so on. Visually, you can think of it as a tree-like structure, with the root at the top and progressively smaller branches extending downward.

This process of dividing continues until the code encounters an exit condition. Once that exit condition is encountered, the code begins returning back up the branches of the tree, merging the branches together as each recursive call returns up the tree.

Recursive functions always have three elements in common (usually in this order):

  1. The exit condition,
  2. The recursive call, and
  3. The work that is done in this recursion.

This is a better pseudocode representation from Wikipedia. See if you can spot the three elements:

function merge_sort(list m)
    // Base case. A list of zero or one elements is sorted, by definition.
    if length of m ≤ 1 then
        return m

    // Recursive case. First, divide the list into equal-sized sublists
    // consisting of the even and odd-indexed elements.
    var left := empty list
    var right := empty list
    for each x with index i in m do
        if i is odd then
            add x to left
        else
            add x to right

    // Recursively sort both sublists.
    left := merge_sort(left)
    right := merge_sort(right)

    // Then merge the now-sorted sublists.
    return merge(left, right)

The merge function merges the lists together while returning up the call tree:

function merge(left, right)
    var result := empty list

    while left is not empty and right is not empty do
        if first(left) ≤ first(right) then
            append first(left) to result
            left := rest(left)
        else
            append first(right) to result
            right := rest(right)

    // Either left or right may have elements left; consume them.
    // (Only one of the following loops will actually be entered.)
    while left is not empty do
        append first(left) to result
        left := rest(left)
    while right is not empty do
        append first(right) to result
        right := rest(right)
    return result

Penjee's blog has some excellent animations that help you visualize this process. Here is one that actually draws a tree like the one I mentioned:

enter image description here

  • Hi @Robert. The exit condition appears to be when ( l >= r ). – Mark Jul 12 '16 at 2:57
  • @Mark: Ah, right. Got bit by the bogus indentation in the question; that's now fixed. – Robert Harvey Jul 12 '16 at 3:01
  • @RobertHarvey, Step 5: Sort the combined list. – Adam Zuckerman Jul 12 '16 at 3:20
  • @AdamZuckerman: That's accomplished in the merge function (not shown here, but it's in the Wikipedia article). – Robert Harvey Jul 12 '16 at 4:16
5

Recursion's general principle is to solve a problem by assuming a smaller problem can be solved, and accounting for the difference between the smaller problem and the one currently being asked to solve.

Many recursive algorithms, e.g. recursive factorial, assume a smaller-by-1 problem and then given that answer, solve the delta between that (smaller by one) answer and the requested answer, e.g. by multiplying the smaller problem's answer by N.

In the case of your question, the approach is to solve not just one but two smaller problems and combine the answer using merge. The smaller problems are subdivisions of the larger problem at m, which is half of the range being asked to solve.

By the way, there are many different ways that merge sort is coded up. It partly depends on whether your language efficiently supports slices of arrays (or not).

If it does, the the merge sort is typically asked to sort a given array at each invocation, where the array to sort is really a subset of a larger array, but once passed as an argument, is seen going from 0 to some .length.

If the language does not allow for slices, as might be the case in your question, then the merge sort is directed to sort an explicitly identified sub range of the array (by passing the additional start (l) and end (r) parameters) instead of turning the portion to sort into another array (slice) and passing only that.

In any case it should be relatively easy to see that m is chosen about half way between l and r. So, the first of the two recursive calls asks to sort subrange l to m, and the second, the subrange from m+1 to r. Once merged, this accomplishes the requested sort of the full l to r subrange that was requested.

The initial call will have l as 0 and r as the full length, so the first call is asked to sort the whole array, and in turn asks its recursive helpers to sort about half the array. They in turn subdivide the slice of the array they are asked to sort into about half as well... Eventually, the whole range of the original array is sorted and merged.

Many recursive algorithms use more than one (self) recursive call. For example, recursive tree traversals operate in a similar manner: A post order traversal visits the node itself last after recursively calling itself on left and on right. You might see the subdivision into two smaller problems more easily with the recursion of a tree traversal because there is much less work involved in identifying the smaller problem to solve first (there's just left and right).

But the merge sort does the same thing: for each range it is asked to sort, it first (using recursive invocation) sorts the left half, then the right half, then merges. It has to identify the halves using a bit of arithmetic, which differentiates it from the otherwise similar patterned tree traversal.


A variant of merge sort could subdivide the array into three slices, sorting each one (recursively, of course) then merging. The merge part would require an additional parameter (for the chosen third portion, e.g. merge(array,l,m,n,r);).

4

Psychologically, recursion in programming is similar to "proof by induction" in mathematics. (In case you're not familiar with proof by induction, it consists in proving "If P is true for n=m then it is true for n=m+1", observing that P is true for n=0 [or n=1, if you prefer], and deducing that P is true for all n).

With mathematical induction, different people think in different ways. For instance, checking for small n first, or taking the big picture and working downwards.

For your recursion, I look at it like this:

  1. Assume that the "inner" mergeSort works.

  2. Read the code and satisfy myself that the mergeSort function works if the inner calls to mergeSort work. This is equivalent to the inductive step in mathematics.

  3. Convince myself that my reasoning isn't circular by finding something different about the "inner" mergeSort. In this case - that the "inner" ones are always smaller.

  4. Note that there is an "innermost", "n=0" case. In your example, it is when 0 items remain to be sorted, I think (or 1: you can check).

  5. The inductive proof is then complete. You might say that the reasoning is not circular, but spiral.

  6. Recursion is always bad practice in software engineering because you are using up an unknown and uncontrolled amount of a resource (the stack) which is finite in size and whose size is determined by engineers crossing their fingers and making a hopeful guess. So there is one more thing to check, and that is the depth of recursion. And this is where the choice of the "middle point" m comes in. The algorithm will work in theory with any value at all of m, but the reason for the half-way value used here is that it makes the next inner mergeSort half the size. The algorithm is still bad engineering in general, but for small numbers of values to be sorted, the depth of recursion is small. For instance, if you limit yourself to sorting no more than 2^64 integers, then your maximum recursion depth is only 64, which is tolerable.

  • 2
    "Recursion is always bad" Try again, maybe with "Recursion can be dangerous." There are languages that do tail call optimization and algorithms that are compatible with it, meaning recursion can be perfectly safe. Merge sort, having 2-3 recursive calls, is, admittedly, not fully compatible with TCO, but merge sort is not all algorithms. – 8bittree Jul 12 '16 at 13:42
  • 1
    @8bittree In this case the size to sort halves on each recursive call so you can sort 2^s items with s stack frames. I think recursion is perfectly fine here, even in a language that doesn't support it nicely. – Solomonoff's Secret Jul 12 '16 at 20:12
  • @Solomonoff'sSecret True, most cases will be able to use merge sort even without TCO. The 2^64 example is a big number, over 18 quintillion. With that many elements, the stack isn't the problem, time and total memory are the problems. Assuming one byte per element, that's over 147 exabytes or almost the estimated total digital information created in 2006. – 8bittree Jul 12 '16 at 20:54
3

I was hoping that someone could provide me with insight as to how I should think about these two recursion calls, and how its obvious it had to be this way.

There are basically two things that you need to master:

  1. You need to be able to recognize that a problem is potentially amenable to a recursive solution.

  2. You need to be able to formulate the recursive solution.

I don't think that there is any special magic formula for learning either of these, except for reading books on algorithmics (especially those written by functional programming experts) ... and practice. With enough practice, it becomes easier to spot the opportunity for recursion, and code it.

Don't be put off that you can't (for example) devise a quicksort or mergesort algorithm from scratch with no clues. Don't forget that the people who first devised these things were really smart people. Normal people like you and me understand these algorithms / this thinking because we read or were taught quicksort, etc. Then we apply the same knowledge to other similar problems.

2

Just to provide a very short answer. This works for most kinds of recursive functions.

You don't need to go through the recursion is your head. You just need to write the function for the given parameter, say a list of elements, while assuming that the function already works if you call it with any smaller list of elements.

Similarly in your mergeSort example, when writing or looking at the function with the given l and r parameters, assume that the function already works for any smaller difference between l and r.

The size of a finite list can't keep getting smaller forever, and neither can the gap between l and r, so you don't need to worry about the recursion going on forever.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.