DSA Quick Sort

How it works

This version uses three-way partitioning inside a copied list and an explicit stack of index intervals. The cursor advances after a smaller or equal value, but stays in place after swapping from the unexamined greater end. That incoming value still needs classification. The middle-position pivot is deterministic, not a guarantee of balanced partitions. The implementation is not stable and should be judged under its actual partition and storage choices.

Run the code

Select Try in playground to load this complete source into the existing Python editor. It does not run automatically; choose Run when ready. These examples use only the Python standard library and small fictional inputs. They do not need database services, extra packages or personal files.

For local work, save the complete source as quick-sort.py and run python quick-sort.py. The local review uses Python 3.12.14; the browser uses the existing Pyodide 0.27.7 runtime. Keep inputs small, respect explicit table/tour budgets and account for recursion limits before increasing a fixture’s size.

Example

def quick_sort(values):
    result = list(values)
    pending = [(0, len(result) - 1)]
    while pending:
        low, high = pending.pop()
        if low >= high:
            continue
        pivot = result[(low + high) // 2]
        smaller = cursor = low
        greater = high
        while cursor <= greater:
            if result[cursor] < pivot:
                result[smaller], result[cursor] = result[cursor], result[smaller]
                smaller += 1
                cursor += 1
            elif result[cursor] > pivot:
                result[cursor], result[greater] = result[greater], result[cursor]
                greater -= 1
            else:
                cursor += 1
        pending.append((low, smaller - 1))
        pending.append((greater + 1, high))
    return result

print(quick_sort([14, 5, 11, 5, 2]))
print(quick_sort([5, 5, 5]))

Expected result

[2, 5, 5, 11, 14]
[5, 5, 5]

The three regions become explicit invariants and all-equal input is handled by one partition pass. The iterative stack avoids Python recursion-limit failures, but it does not remove the possibility of poor partition balance on other inputs.

Time, space and assumptions

Balanced partitions give O(n log n) work, while worst-case time remains O(n²). The returned copy and conservatively bounded explicit interval stack use O(n) space; stability is not promised.