Stackless merge sort
Merge sort divides a list into smaller lists of one or zero items, which are trivially sorted, and then merges them pairwise until one list remains. Here is a typical recursive implementation:
def mergesort(lst):
if len(lst) < 2:
return lst[:]
mid = len(lst) // 2
return merge(mergesort(lst[:mid]), mergesort(lst[mid:]))
Note that the base case returns a copy, not the original list, to be consistent with the general behavior. The merge function is:
def merge(left, right):
merged = []
while left and right:
if left[0] <= right[0]:
merged.append(left.pop(0))
else:
merged.append(right.pop(0))
merged.extend(left)
merged.extend(right)
return merged
For simplicity, we use pop(0) which is inefficient but easily remedied with indexing.
Instead of dividing the list recursively, we can put each item into a list by itself, and then merge them iteratively:
def mergesort_stackless(lst):
queue = [[item] for item in lst]
while len(queue) >= 2:
left = queue.pop()
right = queue.pop()
merged = merge(left, right)
queue.insert(0, merged)
return queue[0]
We maintain the individual lists in a queue. In each iteration, we take two lists from the queue, merge them, and put the combined list back in the queue. Eventually just one list remains, which is the desired result. The queue ensures that smaller lists are merged before larger ones, so that the pair being merged does not become too different in size - unbalanced pairs would degrade runtime.
Checking a test case:
>>> lst = [3, 2, 1, 4, 5]
>>> mergesort_stackless(lst)
[1, 2, 3, 4, 5]