Iterative Quick Sort in Python

from bisect import bisect_left

# Iterative Quick Sort in Python
#
# PURPOSE
# Quick sort partitions around a pivot and sorts the two resulting regions. This iterative
# version stores pending intervals explicitly instead of using recursion.
#
# METHOD
# Choose a median-of-three pivot and partition into less-than, equal-to, and greater-than
# regions. Process the smaller region immediately and defer the larger one to keep the
# explicit stack bounded.
#
# COMPLEXITY
# O(n log n) average time, O(n squared) adversarial worst case. Equal-key input takes O(n).
# O(log n) pending intervals; 64 stack slots cover the supported bounded input lengths. Not
# stable.
#
# CONTRACT
# Sorts ascending in place and returns 0. Three-way partition handles repeated keys
# efficiently. Median-of-three reduces common fixed-endpoint pivot problems but does not
# provide introsort's worst-case guarantee.
# Public APIs infer array lengths except in C, which accepts pointer/length pairs. Vertex
# counts and matrix dimensions remain explicit. Arrays must contain signed 32-bit integers.
# Sorted order, correct tree topology, and caller-owned data-structure invariants are
# preconditions; checking them on every query would change query complexity.
# Scalar and shape checks are included. Value-range checks are included where needed to
# prevent invalid indexing or nontermination. Allocation sizes are capped at 4,000,000
# workspace entries. Arithmetic outside Python raises an error on 32-bit overflow; Python
# uses arbitrary precision. Native allocation failures propagate. In-place outputs may be
# partly updated after arithmetic failure. These are single-threaded, in-memory
# implementations.
#
# LANGUAGE DETAILS
# Python 3.9+: automatic lengths, native lists, arbitrary-precision arithmetic, and
# bisect_left for LIS. Invalid scalar/shape inputs raise ValueError. Integer element types
# and sorted/tree invariants remain caller preconditions.
#
# EXAMPLE
# Expected return: 0.
# Expected a after call: [1, 1, 3, 5].
# Run: python example.py
# Tests for this exact source artifact run before publication. The accompanying source
# archive includes unit cases, runtime results, and source hashes.

def alg_require(condition):
    if not condition:
        raise ValueError("invalid algorithm input; see contract")
def alg_size(n):
    alg_require(0 <= n <= 4000000)
    return n

def quick_sort(a: list[int]) -> int:
    alg_require(isinstance(a, list) and len(a) <= 1000000)
    n: int = len(a)
    alg_require(n >= 0 and n <= 1000000)
    alg_require(len(a) == n)
    lefts: list[int] = [0] * alg_size(64)
    rights: list[int] = [0] * alg_size(64)
    top: int = 0
    low: int = 0
    high: int = n - 1
    left: int = 0
    right: int = 0
    mid: int = 0
    pivot: int = 0
    temp: int = 0
    while low < high or top > 0:
        if low >= high:
            top -= 1
            low = lefts[top]
            high = rights[top]
        mid = low + (high - low) // 2
        pivot = max(min(a[low], a[mid]), min(max(a[low], a[mid]), a[high]))
        left = low
        mid = low
        right = high
        while mid <= right:
            if a[mid] < pivot:
                temp = a[left]
                a[left] = a[mid]
                a[mid] = temp
                left += 1
                mid += 1
            elif a[mid] > pivot:
                temp = a[mid]
                a[mid] = a[right]
                a[right] = temp
                right -= 1
            else:
                mid += 1
        if left - low < high - right:
            if right + 1 < high:
                lefts[top] = right + 1
                rights[top] = high
                top += 1
            high = left - 1
        else:
            if low < left - 1:
                lefts[top] = low
                rights[top] = left - 1
                top += 1
            low = right + 1
    return 0

a = [5, 1, 3, 1]
result = quick_sort(a)
print(result)
print(a)
# Expected a: [1, 1, 3, 5]