Stackless Quicksort

Quicksort is a famous example of a recursive algorithm. Here is a sub-optimal implementation:

def qsort(lst, start=0, end=None):
    if end is None:
        end = len(lst)
    if end - start < 2:
        return

    pivot_position = partition(lst, start, end)

    qsort(lst, start, pivot_position)
    qsort(lst, pivot_position + 1, end)

The partition function chooses a pivot value and places it at the correct position, with smaller values to its left and larger values to its right. It also returns the final position of the pivot value.

def partition(lst, start, end):
    pivot = lst[start]
    rest = lst[start + 1 : end]

    left = [item for item in rest if item <= pivot]
    right = [item for item in rest if item > pivot]

    lst[start:end] = left + [pivot] + right
    return start + len(left)

For brevity, we use list slicing instead of swaps, but the discussion does not depend on how the partitioning is done.

In the above implementation, observe that each recursive call stands alone, simply sorting a segment of the list. As this article points out, the recursive call stack serves merely to ensure that the list is divided into smaller segments until every item is a pivot or belongs to a segment of one item.

Because the order in which different parts of the list is sorted is immaterial, we don’t need recursion or even a stack for that matter. Here is an implementation of quicksort using a set to track which segments are still to be sorted:

def qsort_stackless(lst):
    not_sorted = {(0, len(lst))}

    while not_sorted:
        start, end = not_sorted.pop()
        pivot_position = partition(lst, start, end)
        if pivot_position - start > 0:
            not_sorted.add((start, pivot_position))
        if end - (pivot_position + 1) > 0:
            not_sorted.add((pivot_position + 1, end))

The set not_sorted contains start and end indices of segments which remain to be sorted. Note that the pop method returns an arbitrary element of a set, which becomes empty when no unsorted segments remain. The list is then sorted. Let’s check a test case:

>>> lst = [3, 2, 1, 4, 5]
>>> qsort_stackless(lst)
>>> lst[1, 2, 3, 4, 5]