# Generated by tools/algo/legacy.py from the corpus: do not edit.
# The /compare page's quicksort: Lomuto's partition around the last element.
# Element comparisons are routed through lib/algo/legacy/order.viv; nothing else changes.
from algo.legacy.order import lg_lt

# from study/compare/recursion/quicksort.viv: partition quicksort

def partition(a, lo, hi) {
    pivot = a[hi]
    i = lo
    for j from lo to hi {
        if lg_lt(a[j], pivot) {
            a[i], a[j] = a[j], a[i]
            i += 1
        }
    }
    a[i], a[hi] = a[hi], a[i]
    return i
}

def quicksort(a, lo, hi) {
    if lo < hi {
        p = partition(a, lo, hi)
        quicksort(a, lo, p - 1)
        quicksort(a, p + 1, hi)
    }
}