Iterative and/or tail-recursive implementations of merge sort?

I recently learned how to implement merge-sort, using a standard recursive algorithm. Can the algorithm be implemented in a way that allows for a tail-recursive implementation? Can it be implemented in an iterative style?

In general how can a recursive algorithm converted into an iterative and tail-recursive algorithm? What are the possible pros and cons of this conversion?

An iterative implementation is easy: you just introduce an explicit stack (instead of using the call stack as the implicit stack). You can always convert any recursive algorithm to be in iterative form by using an explicit stack; each recursive call is translated into pushing something onto the stack.

However, I don't know of any reason why you'd want to do that, in this case; the resulting algorithm just becomes harder to understand. The amount of stack space used by merge-sort is $O(\lg n)$, where $n$ is the length of the list, so you're not going to exhaust the size of the available stack.

Merge-sort is not purely tail-recursive. First of all, the result of a call to merge-sort is not the result of either recursive call; the results of the two recursive calls must be further processed (by merging the sorted sublists). Second of all, merge-sort contains two recursive calls, so even if there were some way to convert the last call to a tail-call (there isn't), you'd still be left with one other recursive call inside the body of the function. So, no, merge-sort is not tail-recursive. And there's little or no benefit to try to rewrite it in a form that is tail-recursive.

(Technically speaking, just as any algorithm can be transformed to be iterative, anything can be transformed to be tail-recursive form by using continuation-passing style. This includes merge-sort. Nonetheless, in this case there is no reason why anyone would want to do that. It's unlikely to make the code noticeably faster, and it's sure to make the code harder to understand. Therefore, this is a technicality that can be safely ignored. If you don't know what continuation-passing style is, don't worry about it, you can just pretend that merge-sort cannot be made tail-recursive, and that'll be close enough.)

• Anything can be made tail-recursive if you use Continuation Passing Style. – jmite Jul 8 '13 at 2:14
• @jmite, yes, I know (just as anything can be made iterative by introducing an explicit stack). I never claimed to the contrary. Nonetheless, the standard algorithm is not tail-recursive; and there is no practical reason to transform it to be tail-recursive by using CPS. I've edited my answer to incorporate your point, even though I think it's likely to be a distraction for the purposes of the original question (about merge-sort). – D.W. Jul 8 '13 at 2:43
• The practical reason to transform it is so that you can have explicit control over the program control flow. – jmite Jul 8 '13 at 19:58

As DW says, the iterative version is fairly easy. The way to convert recursion into iteration is by using a stack, which emulates the call stack for function calls.

As I alluded to in my comment, to convert it to tail-recursive form, you'll need a language with first-class functions so that you can build continuations.

In CPS, you add an extra argument to each function, which is the continuation, representing the instructions to do next.

Each recursive "base case" of (lambda x (baseCase)) turns into (lambda x k (k baseCase)) i.e. you pass the base case value as the argument to the continuation.

Each recursive call then turns into "recursively call this function after adding another instruction to the continuation." You directly call your function recursively, but pass a different value of k (the continuation) which is a new function redefined to incorporate the operations you do in the recursive case.

There's more in this Wikipedia article.

• So I guess C is out of the picture to implement a tail-recursive version of merge sort. Thanks for the info. – Aseem Bansal Jul 9 '13 at 6:21

I find iterative merge sort somewhat easier to read than the recursive version.

I Googled "iterative merge sort" and found this c# iterative implementation.

Recursive merge sort is somewhat more cache friendly than iterative merge sort. There is a big difference between the order in which this iterative merge sort algorithm touches data elements and the order in which recursive merge sort touches data elements. (Although merge sort isn't very cache friendly compared to an in-place sort like randomized quick sort. And your version of merge_parts does an extra array copy which is yet less cache friendly.)

So something like this (I'm sure I've got some off-by-one errors, but this is the basic idea):

// each outer loop iteration merges together subarrays that are twice as large
for (subLength = 1; subLength < arrayLength; subLength = subLength * 2):
swap(inputArray, outputArray)
// iterate through entire array (which is "cache unfriendly")
for (i = 0; (i + subLength) < arrayLength; i = i + (2 * subLength)):
end = min(i + (2*subLength), arrayLength)
mid = i + subLength
mergeParts(inputArray, outputArray,
i, mid, end)


and mergeParts here merges inputArray[i...mid-1] with inputArray[mid...end-1] placing the result in outputArray[i...end-1].

• "There is a big difference between the order in which iterative merge sort touches data elements and the order in which recursive merge sort touches data elements." - This may be slightly misleading. There's a big difference between the order in which the standard recursive version touches data and the order in which one particular iterative implementation touches data. But there are many ways to make an "iterative mergesort", and they don't all touch data in the same order. It's possible to build an iterative mergesort that touches data in exactly the same order as recursive mergesort. – D.W. Jul 8 '13 at 2:48
• @D.W. Yes, I understand that I oversimplified. But the OP's original question (before your edits) asked about the pros and cons of iterative vs. recursive mergesort, not about the pros and cons of the automatic conversion of recursion to iteration by introducing an explicit stack (or via CPS). To do the conversion I did automatically you would also need to perform a proof in the compiler about the dependencies between "adjacent" calls a-la Rugina and Rinard, PPoPP, 1999. – Wandering Logic Jul 8 '13 at 10:50
• I would further argue that any natural iterative version of quicksort would be a doubly-nested loop where the inner loop touches every element of the array. – Wandering Logic Jul 8 '13 at 10:51
• "Although merge sort isn't very cache friendly compared to an in-place sort like randomized quick sort." This seems wrong to me. It's well known that heapsort is not cache-friendly, even if it requires O(1) memory[note: quicksort uses O(log(n)) memory so, depending on the definition of "in-place" it may not even be an in-place algorithm!] – Bakuriu Jul 8 '13 at 19:02