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

Problem Detail: 

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?

Asked By : Aseem Bansal

Answered By : D.W.

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/13139