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.