Quicksort (recursive)

# Self-authored for the EML case corpus (no external origin). Recursive
# quicksort over a fixed sample list via Lomuto-style in-place partitioning
# — a different recursive-sort strategy from examples/merge-sort/ (mutates
# the list in place through subscript assignment, rather than building new
# lists via `+`).

def partition(items, low, high):
    items[high] => pivot
    low - 1 => i
    low => j
    while j < high:
        if items[j] <= pivot:
            i + 1 => i
            items[i] => temp_i
            items[j] => temp_j
            temp_j => items[i]
            temp_i => items[j]
        j + 1 => j
    i + 1 => i
    items[i] => temp_i
    items[high] => temp_high
    temp_high => items[i]
    temp_i => items[high]
    return i

def quicksort(items, low, high):
    if low < high:
        partition(items, low, high) => pivot_index
        quicksort(items, low, pivot_index - 1)
        quicksort(items, pivot_index + 1, high)
    return items

numbers^+[5, 2, 9, 1, 5, 6, 3, 8, 4]
len(numbers) => n
"Before: " + str(numbers) => msg1
msg1^0
quicksort(numbers, 0, n - 1) => sorted_numbers
"After:  " + str(sorted_numbers) => msg2
msg2^0

def partition(items, low, high):
    pivot = items[high]
    i = low - 1
    j = low
    while j < high:
        if items[j] <= pivot:
            i = i + 1
            temp_i = items[i]
            temp_j = items[j]
            items[i] = temp_j
            items[j] = temp_i
        j = j + 1
    i = i + 1
    temp_i = items[i]
    temp_high = items[high]
    items[i] = temp_high
    items[high] = temp_i
    return i

def quicksort(items, low, high):
    if low < high:
        pivot_index = partition(items, low, high)
        quicksort(items, low, pivot_index - 1)
        quicksort(items, pivot_index + 1, high)
    return items

numbers = [5, 2, 9, 1, 5, 6, 3, 8, 4]
n = len(numbers)
msg1 = "Before: " + str(numbers)
print(msg1)
sorted_numbers = quicksort(numbers, 0, n - 1)
msg2 = "After:  " + str(sorted_numbers)
print(msg2)

Before: [5, 2, 9, 1, 5, 6, 3, 8, 4]
After:  [1, 2, 3, 4, 5, 5, 6, 8, 9]

Trace event types