5

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).

5
  • 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, 2016 at 14:09
  • Are you familar with proofs by induction in math? Jul 12, 2016 at 14:30
  • @RemcoGerlich Yes. Why?
    – DLV
    Jul 12, 2016 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, 2016 at 17:31
  • 1
    You can think of it as like a reduce operation Jul 12, 2016 at 23:27

6 Answers 6

6

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

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

3
  • 3
    "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, 2016 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. Jul 12, 2016 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, 2016 at 20:54
4

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.

0
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.

0

It took me a while to piece it together. It's not as natural as a normal fibonacci or tree operations.

Answer1: Drawing and figuring out the order.

Robert Harvey's answer really helped me get on track.

First tip. Try paper. How you outline things on paper are critical for understanding it.

My answer is based off of the following PDF from University of Purdue. Once you see that diagram, you then need to understand the order of operations. Otherwise you won't be able to put it together.

enter image description here

Notice the green numbers. That's exactly the order that a merge sort recursively computes its result.

It's recursively splitting til it gets to a leaf (array with a count of 1) and creeping back up then. You basically first try to get to the bottom left leaf and every other leaf from the left and come back up, til you get to the right side. The right side (of the original array) doesn't start until the entirety of the left side is done. Then all the right side goes on, until both sides have a sorted array and then you sort them against one another as the last step.

Steps 5,10, 11 are the only steps that are backwards.

Make sure you see that pdf. It has a lot of single step slides. Make it much easier to comprehend.


Answer2: Think of this answer more as a series of comments:

I came to this question and some other links to figure it out. This is how I answer it:

Do you know how to merge two (sorted) arrays?

[2, 18, 30] & [5, 9, 22].

You just keep comparing the first item and putting into a new sorted array

Do you know how to split an array into two sections?

Just split from the middle

What needs to be done on each split?

Need to perform mergeSort, otherwise your two arrays won't be sorted. This is the heart of it, but also where you don't need to care of its details, until you get to implementation details.

We need a base i.e. one that shouldn't call anything else recursively. Do you know how you get to that?

We just get to it by splitting enough till there's only a single item in the array. Where it can't be split.

What's also tricky is: With the exception of where the array's length is less than 2, The the base case while it returns, is never meant to be the answer. It's just an intermediate array for comparison.

This is similar to what Robert Harvey said in his answer:

Visually, you can think of it as a tree-like structure, with the root at the top and progressively smaller branches extending downward.

i.e. you need the answers of the leafs to be able to get the answer of the root.

Do you know how to test the logic of it as a whole?

Yeah, just I'll just use a [3,2] array. Split it in two. [3] & [2] and then start comparing from the first item in each array and place them in a sorted array.

Sample Swift code:

func mergeSort(array: [Int]) -> [Int] {
    // 1. base case
    guard array.count > 1 else { 
        return array
    }
    let leftArray = Array(array[0..<array.count / 2])
    let rightArray = Array(array[array.count / 2..<array.count])
    // 2. recursive call
    return merge(left: mergeSort(array: leftArray), right: mergeSort(array: rightArray))
}


// 3. work done in each iteration
func merge(left: [Int], right: [Int]) -> [Int] {
    var left = left
    var right = right
    var sorted: [Int] = []
    
    while left.count > 0 && right.count > 0 {
        if right.first! >= left.first! {
            sorted.append(left.removeFirst())
        } else {
            sorted.append(right.removeFirst())
        }
    } 
    sorted += left + right
    return sorted
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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