alternative to recursion based merge sort logic

Question

here is a merge sort logic in python : (this is the first part, ignore the function merge()) The point in question is converting the recursive logic to a while loop. Code courtesy: Rosettacode Merge Sort

def merge_sort(m):
    if len(m) <= 1:
        return m

    middle = len(m) / 2
    left = m[:middle]
    right = m[middle:]

    left = merge_sort(left)
    right = merge_sort(right)
    return list(merge(left, right))

Is it possible to make it a sort of dynamically in the while loop while each left and right array breaks into two, a sort of pointer keeps increasing based on the number of left and right arrays and breaking them until only single length sized list remains? because every time the next split comes while going on both left- and right- side the array keeps breaking down till only single length list remains, so the number of left sided (left-left,left-right) and right sided (right-left,right-right) breaks will increase till it reaches a list of size 1 for all.

Answer 1

One possible implementation might be this:

def merge_sort(m):
    l = [[x] for x in m]                  # split each element to its own list
    while len(l) > 1:                     # while there's merging to be done 
        for x in range(len(l) >> 1):      # take the first len/2 lists
            l[x] = merge(l[x], l.pop())   # and merge with the last len/2 lists
    return l[0] if len(l) else []

Stack frames in the recursive version are used to store progressively smaller lists that need to be merged. You correctly identified that at the bottom of the stack, there's a one-element list for each element in whatever you're sorting. So, by starting from a series of one-element lists, we can iteratively build up larger, merged lists until we have a single, sorted list.

Answer 2

Reposted from alternative to recursion based merge sort logic at the request of a reader:

One way to eliminate recursion is to use a queue to manage the outstanding work. For example, using the built-in collections.deque:

from collections import deque
from heapq import merge

def merge_sorted(iterable):
    """Return a list consisting of the sorted elements of 'iterable'."""
    queue = deque([i] for i in iterable)
    if not queue:
        return []
    while len(queue) > 1:
        queue.append(list(merge(queue.popleft(), queue.popleft())))
    return queue[0]

Answer 3

It's said, that every recursive function can be written in a non-recursive manner, so the short answer is: yes, it's possible. The only solution I can think of is to use the stack-based approach. When recursive function invokes itself, it puts some context (its arguments and return address) on the inner stack, which isn't available for you. Basically, what you need to do in order to eliminate recursion is to write your own stack and every time when you would make a recursive call, put the arguments onto this stack.

For more information you can read this article, or refer to the section named 'Eliminating Recursion' in Robert Lafore's "Data Structures and Algorithms in Java" (although all the examples in this book are given in Java, it's pretty easy to grasp the main idea).

Answer 4

Going with Dan's solution above and taking the advice on pop, still I tried eliminating while and other not so pythonic approach. Here is a solution that I have suggested: PS: l = len

My doubt on Dans solution is what if L.pop() and L[x] are same and a conflict is created, as in the case of an odd range after iterating over half of the length of L?

def merge_sort(m):
    L = [[x] for x in m]  # split each element to its own list
    for x in xrange(l(L)):      
        if x > 0:
            L[x] = merge(L[x-1], L[x])
    return L[-1]

This can go on for all academic discussions but I got my answer to an alternative to recursive method.