non-recursive quicksort, based on http://bertrandmeyer.com/2014/12/07/lampsort/

lampsort

from collections import deque

def partition(a, lo, hi):
    """partition a[lo] to a[hi] using a[hi] as the pivot"""
    pivot_value = a[hi]
    insert_at = lo
    for i in range(lo, hi):
        if a[i] < pivot_value:
            a[i], a[insert_at] = a[insert_at], a[i]
            insert_at += 1
    a[hi], a[insert_at] = a[insert_at], a[hi]
    return insert_at

def lampsort(a):
    """non-recursive quicksort using a deque of intervals
    see http://bertrandmeyer.com/2014/12/07/lampsort/"""
    intervals = deque([(0, len(a) - 1)])
    
    while intervals:
        lo, hi = intervals.popleft()
        
        if lo >= hi: continue
        
        pivot = partition(a, lo, hi)
        intervals.append((lo, pivot - 1))
        intervals.append((pivot + 1, hi))