Quick Sort

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, len(nums)-1).
func quickSort(nums []int, lo, hi int) {

}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, len(nums)-1).
func quickSort(nums []int, lo, hi int) {
    // Divide and conquer. Base case: a range of 0 or 1 element is already
    // sorted, so there's nothing to do.
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, len(nums)-1).
func quickSort(nums []int, lo, hi int) {
    // Divide and conquer. Base case: a range of 0 or 1 element is already
    // sorted, so there's nothing to do.
    if lo >= hi {
        return
    }
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, len(nums)-1).
func quickSort(nums []int, lo, hi int) {
    // Divide and conquer. Base case: a range of 0 or 1 element is already
    // sorted, so there's nothing to do.
    if lo >= hi {
        return
    }

    // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
    // returning the index p the pivot lands on. Afterwards everything left of p
    // is < pivot, everything right is >= pivot, and the pivot sits in its final
    // sorted position.
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, len(nums)-1).
func quickSort(nums []int, lo, hi int) {
    // Divide and conquer. Base case: a range of 0 or 1 element is already
    // sorted, so there's nothing to do.
    if lo >= hi {
        return
    }

    // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
    // returning the index p the pivot lands on. Afterwards everything left of p
    // is < pivot, everything right is >= pivot, and the pivot sits in its final
    // sorted position.
    p := partition(nums, lo, hi)
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, len(nums)-1).
func quickSort(nums []int, lo, hi int) {
    // Divide and conquer. Base case: a range of 0 or 1 element is already
    // sorted, so there's nothing to do.
    if lo >= hi {
        return
    }

    // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
    // returning the index p the pivot lands on. Afterwards everything left of p
    // is < pivot, everything right is >= pivot, and the pivot sits in its final
    // sorted position.
    p := partition(nums, lo, hi)

    // The pivot at p is already correct, so recurse on the two sides only —
    // never on p itself. That shrinking range is what guarantees termination.
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, len(nums)-1).
func quickSort(nums []int, lo, hi int) {
    // Divide and conquer. Base case: a range of 0 or 1 element is already
    // sorted, so there's nothing to do.
    if lo >= hi {
        return
    }

    // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
    // returning the index p the pivot lands on. Afterwards everything left of p
    // is < pivot, everything right is >= pivot, and the pivot sits in its final
    // sorted position.
    p := partition(nums, lo, hi)

    // The pivot at p is already correct, so recurse on the two sides only —
    // never on p itself. That shrinking range is what guarantees termination.
    quickSort(nums, lo, p-1)
    quickSort(nums, p+1, hi)
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, len(nums)-1).
func quickSort(nums []int, lo, hi int) {
    // Divide and conquer. Base case: a range of 0 or 1 element is already
    // sorted, so there's nothing to do.
    if lo >= hi {
        return
    }

    // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
    // returning the index p the pivot lands on. Afterwards everything left of p
    // is < pivot, everything right is >= pivot, and the pivot sits in its final
    // sorted position.
    p := partition(nums, lo, hi)

    // The pivot at p is already correct, so recurse on the two sides only —
    // never on p itself. That shrinking range is what guarantees termination.
    quickSort(nums, lo, p-1)
    quickSort(nums, p+1, hi)
}

// Lomuto partition scheme — the simplest way to partition. It takes the LAST
// element as the pivot and makes a single left-to-right pass, keeping a boundary
// between "seen values that are < pivot" and everything else. (The alternative,
// Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
// right. Lomuto is the one to memorize first.)

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, len(nums)-1).
func quickSort(nums []int, lo, hi int) {
    // Divide and conquer. Base case: a range of 0 or 1 element is already
    // sorted, so there's nothing to do.
    if lo >= hi {
        return
    }

    // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
    // returning the index p the pivot lands on. Afterwards everything left of p
    // is < pivot, everything right is >= pivot, and the pivot sits in its final
    // sorted position.
    p := partition(nums, lo, hi)

    // The pivot at p is already correct, so recurse on the two sides only —
    // never on p itself. That shrinking range is what guarantees termination.
    quickSort(nums, lo, p-1)
    quickSort(nums, p+1, hi)
}

// Lomuto partition scheme — the simplest way to partition. It takes the LAST
// element as the pivot and makes a single left-to-right pass, keeping a boundary
// between "seen values that are < pivot" and everything else. (The alternative,
// Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
// right. Lomuto is the one to memorize first.)
func partition(nums []int, lo, hi int) int {
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, len(nums)-1).
func quickSort(nums []int, lo, hi int) {
    // Divide and conquer. Base case: a range of 0 or 1 element is already
    // sorted, so there's nothing to do.
    if lo >= hi {
        return
    }

    // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
    // returning the index p the pivot lands on. Afterwards everything left of p
    // is < pivot, everything right is >= pivot, and the pivot sits in its final
    // sorted position.
    p := partition(nums, lo, hi)

    // The pivot at p is already correct, so recurse on the two sides only —
    // never on p itself. That shrinking range is what guarantees termination.
    quickSort(nums, lo, p-1)
    quickSort(nums, p+1, hi)
}

// Lomuto partition scheme — the simplest way to partition. It takes the LAST
// element as the pivot and makes a single left-to-right pass, keeping a boundary
// between "seen values that are < pivot" and everything else. (The alternative,
// Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
// right. Lomuto is the one to memorize first.)
func partition(nums []int, lo, hi int) int {
    // Pivot = the last element. Any element works; picking the last one is
    // simplest, but on already-sorted input it causes the O(n^2) worst case —
    // production code often picks a random or median-of-three pivot instead.
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, len(nums)-1).
func quickSort(nums []int, lo, hi int) {
    // Divide and conquer. Base case: a range of 0 or 1 element is already
    // sorted, so there's nothing to do.
    if lo >= hi {
        return
    }

    // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
    // returning the index p the pivot lands on. Afterwards everything left of p
    // is < pivot, everything right is >= pivot, and the pivot sits in its final
    // sorted position.
    p := partition(nums, lo, hi)

    // The pivot at p is already correct, so recurse on the two sides only —
    // never on p itself. That shrinking range is what guarantees termination.
    quickSort(nums, lo, p-1)
    quickSort(nums, p+1, hi)
}

// Lomuto partition scheme — the simplest way to partition. It takes the LAST
// element as the pivot and makes a single left-to-right pass, keeping a boundary
// between "seen values that are < pivot" and everything else. (The alternative,
// Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
// right. Lomuto is the one to memorize first.)
func partition(nums []int, lo, hi int) int {
    // Pivot = the last element. Any element works; picking the last one is
    // simplest, but on already-sorted input it causes the O(n^2) worst case —
    // production code often picks a random or median-of-three pivot instead.
    pivot := nums[hi]
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, len(nums)-1).
func quickSort(nums []int, lo, hi int) {
    // Divide and conquer. Base case: a range of 0 or 1 element is already
    // sorted, so there's nothing to do.
    if lo >= hi {
        return
    }

    // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
    // returning the index p the pivot lands on. Afterwards everything left of p
    // is < pivot, everything right is >= pivot, and the pivot sits in its final
    // sorted position.
    p := partition(nums, lo, hi)

    // The pivot at p is already correct, so recurse on the two sides only —
    // never on p itself. That shrinking range is what guarantees termination.
    quickSort(nums, lo, p-1)
    quickSort(nums, p+1, hi)
}

// Lomuto partition scheme — the simplest way to partition. It takes the LAST
// element as the pivot and makes a single left-to-right pass, keeping a boundary
// between "seen values that are < pivot" and everything else. (The alternative,
// Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
// right. Lomuto is the one to memorize first.)
func partition(nums []int, lo, hi int) int {
    // Pivot = the last element. Any element works; picking the last one is
    // simplest, but on already-sorted input it causes the O(n^2) worst case —
    // production code often picks a random or median-of-three pivot instead.
    pivot := nums[hi]

    // i is the boundary of the "< pivot" region: everything in nums[lo..i) is
    // known to be smaller than the pivot. It starts empty (i == lo).
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, len(nums)-1).
func quickSort(nums []int, lo, hi int) {
    // Divide and conquer. Base case: a range of 0 or 1 element is already
    // sorted, so there's nothing to do.
    if lo >= hi {
        return
    }

    // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
    // returning the index p the pivot lands on. Afterwards everything left of p
    // is < pivot, everything right is >= pivot, and the pivot sits in its final
    // sorted position.
    p := partition(nums, lo, hi)

    // The pivot at p is already correct, so recurse on the two sides only —
    // never on p itself. That shrinking range is what guarantees termination.
    quickSort(nums, lo, p-1)
    quickSort(nums, p+1, hi)
}

// Lomuto partition scheme — the simplest way to partition. It takes the LAST
// element as the pivot and makes a single left-to-right pass, keeping a boundary
// between "seen values that are < pivot" and everything else. (The alternative,
// Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
// right. Lomuto is the one to memorize first.)
func partition(nums []int, lo, hi int) int {
    // Pivot = the last element. Any element works; picking the last one is
    // simplest, but on already-sorted input it causes the O(n^2) worst case —
    // production code often picks a random or median-of-three pivot instead.
    pivot := nums[hi]

    // i is the boundary of the "< pivot" region: everything in nums[lo..i) is
    // known to be smaller than the pivot. It starts empty (i == lo).
    i := lo
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, len(nums)-1).
func quickSort(nums []int, lo, hi int) {
    // Divide and conquer. Base case: a range of 0 or 1 element is already
    // sorted, so there's nothing to do.
    if lo >= hi {
        return
    }

    // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
    // returning the index p the pivot lands on. Afterwards everything left of p
    // is < pivot, everything right is >= pivot, and the pivot sits in its final
    // sorted position.
    p := partition(nums, lo, hi)

    // The pivot at p is already correct, so recurse on the two sides only —
    // never on p itself. That shrinking range is what guarantees termination.
    quickSort(nums, lo, p-1)
    quickSort(nums, p+1, hi)
}

// Lomuto partition scheme — the simplest way to partition. It takes the LAST
// element as the pivot and makes a single left-to-right pass, keeping a boundary
// between "seen values that are < pivot" and everything else. (The alternative,
// Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
// right. Lomuto is the one to memorize first.)
func partition(nums []int, lo, hi int) int {
    // Pivot = the last element. Any element works; picking the last one is
    // simplest, but on already-sorted input it causes the O(n^2) worst case —
    // production code often picks a random or median-of-three pivot instead.
    pivot := nums[hi]

    // i is the boundary of the "< pivot" region: everything in nums[lo..i) is
    // known to be smaller than the pivot. It starts empty (i == lo).
    i := lo

    // Scan every element before the pivot with j.
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, len(nums)-1).
func quickSort(nums []int, lo, hi int) {
    // Divide and conquer. Base case: a range of 0 or 1 element is already
    // sorted, so there's nothing to do.
    if lo >= hi {
        return
    }

    // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
    // returning the index p the pivot lands on. Afterwards everything left of p
    // is < pivot, everything right is >= pivot, and the pivot sits in its final
    // sorted position.
    p := partition(nums, lo, hi)

    // The pivot at p is already correct, so recurse on the two sides only —
    // never on p itself. That shrinking range is what guarantees termination.
    quickSort(nums, lo, p-1)
    quickSort(nums, p+1, hi)
}

// Lomuto partition scheme — the simplest way to partition. It takes the LAST
// element as the pivot and makes a single left-to-right pass, keeping a boundary
// between "seen values that are < pivot" and everything else. (The alternative,
// Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
// right. Lomuto is the one to memorize first.)
func partition(nums []int, lo, hi int) int {
    // Pivot = the last element. Any element works; picking the last one is
    // simplest, but on already-sorted input it causes the O(n^2) worst case —
    // production code often picks a random or median-of-three pivot instead.
    pivot := nums[hi]

    // i is the boundary of the "< pivot" region: everything in nums[lo..i) is
    // known to be smaller than the pivot. It starts empty (i == lo).
    i := lo

    // Scan every element before the pivot with j.
    for j := lo; j < hi; j++ {
    }
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, len(nums)-1).
func quickSort(nums []int, lo, hi int) {
    // Divide and conquer. Base case: a range of 0 or 1 element is already
    // sorted, so there's nothing to do.
    if lo >= hi {
        return
    }

    // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
    // returning the index p the pivot lands on. Afterwards everything left of p
    // is < pivot, everything right is >= pivot, and the pivot sits in its final
    // sorted position.
    p := partition(nums, lo, hi)

    // The pivot at p is already correct, so recurse on the two sides only —
    // never on p itself. That shrinking range is what guarantees termination.
    quickSort(nums, lo, p-1)
    quickSort(nums, p+1, hi)
}

// Lomuto partition scheme — the simplest way to partition. It takes the LAST
// element as the pivot and makes a single left-to-right pass, keeping a boundary
// between "seen values that are < pivot" and everything else. (The alternative,
// Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
// right. Lomuto is the one to memorize first.)
func partition(nums []int, lo, hi int) int {
    // Pivot = the last element. Any element works; picking the last one is
    // simplest, but on already-sorted input it causes the O(n^2) worst case —
    // production code often picks a random or median-of-three pivot instead.
    pivot := nums[hi]

    // i is the boundary of the "< pivot" region: everything in nums[lo..i) is
    // known to be smaller than the pivot. It starts empty (i == lo).
    i := lo

    // Scan every element before the pivot with j.
    for j := lo; j < hi; j++ {
        // Does nums[j] belong in the "< pivot" region? If so, swap it to the
        // boundary (position i), which places it just past the known-smaller run.

            // The region grew by one, so advance the boundary.
    }
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, len(nums)-1).
func quickSort(nums []int, lo, hi int) {
    // Divide and conquer. Base case: a range of 0 or 1 element is already
    // sorted, so there's nothing to do.
    if lo >= hi {
        return
    }

    // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
    // returning the index p the pivot lands on. Afterwards everything left of p
    // is < pivot, everything right is >= pivot, and the pivot sits in its final
    // sorted position.
    p := partition(nums, lo, hi)

    // The pivot at p is already correct, so recurse on the two sides only —
    // never on p itself. That shrinking range is what guarantees termination.
    quickSort(nums, lo, p-1)
    quickSort(nums, p+1, hi)
}

// Lomuto partition scheme — the simplest way to partition. It takes the LAST
// element as the pivot and makes a single left-to-right pass, keeping a boundary
// between "seen values that are < pivot" and everything else. (The alternative,
// Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
// right. Lomuto is the one to memorize first.)
func partition(nums []int, lo, hi int) int {
    // Pivot = the last element. Any element works; picking the last one is
    // simplest, but on already-sorted input it causes the O(n^2) worst case —
    // production code often picks a random or median-of-three pivot instead.
    pivot := nums[hi]

    // i is the boundary of the "< pivot" region: everything in nums[lo..i) is
    // known to be smaller than the pivot. It starts empty (i == lo).
    i := lo

    // Scan every element before the pivot with j.
    for j := lo; j < hi; j++ {
        // Does nums[j] belong in the "< pivot" region? If so, swap it to the
        // boundary (position i), which places it just past the known-smaller run.
        if nums[j] < pivot {
            nums[i], nums[j] = nums[j], nums[i]

            // The region grew by one, so advance the boundary.
            i++
        }
    }
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, len(nums)-1).
func quickSort(nums []int, lo, hi int) {
    // Divide and conquer. Base case: a range of 0 or 1 element is already
    // sorted, so there's nothing to do.
    if lo >= hi {
        return
    }

    // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
    // returning the index p the pivot lands on. Afterwards everything left of p
    // is < pivot, everything right is >= pivot, and the pivot sits in its final
    // sorted position.
    p := partition(nums, lo, hi)

    // The pivot at p is already correct, so recurse on the two sides only —
    // never on p itself. That shrinking range is what guarantees termination.
    quickSort(nums, lo, p-1)
    quickSort(nums, p+1, hi)
}

// Lomuto partition scheme — the simplest way to partition. It takes the LAST
// element as the pivot and makes a single left-to-right pass, keeping a boundary
// between "seen values that are < pivot" and everything else. (The alternative,
// Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
// right. Lomuto is the one to memorize first.)
func partition(nums []int, lo, hi int) int {
    // Pivot = the last element. Any element works; picking the last one is
    // simplest, but on already-sorted input it causes the O(n^2) worst case —
    // production code often picks a random or median-of-three pivot instead.
    pivot := nums[hi]

    // i is the boundary of the "< pivot" region: everything in nums[lo..i) is
    // known to be smaller than the pivot. It starts empty (i == lo).
    i := lo

    // Scan every element before the pivot with j.
    for j := lo; j < hi; j++ {
        // Does nums[j] belong in the "< pivot" region? If so, swap it to the
        // boundary (position i), which places it just past the known-smaller run.
        if nums[j] < pivot {
            nums[i], nums[j] = nums[j], nums[i]

            // The region grew by one, so advance the boundary.
            i++
        }
    }

    // The scan is done: nums[lo..i) < pivot and nums[i..hi) >= pivot, so index i
    // is exactly where the pivot belongs. Swap it in from the end.
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, len(nums)-1).
func quickSort(nums []int, lo, hi int) {
    // Divide and conquer. Base case: a range of 0 or 1 element is already
    // sorted, so there's nothing to do.
    if lo >= hi {
        return
    }

    // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
    // returning the index p the pivot lands on. Afterwards everything left of p
    // is < pivot, everything right is >= pivot, and the pivot sits in its final
    // sorted position.
    p := partition(nums, lo, hi)

    // The pivot at p is already correct, so recurse on the two sides only —
    // never on p itself. That shrinking range is what guarantees termination.
    quickSort(nums, lo, p-1)
    quickSort(nums, p+1, hi)
}

// Lomuto partition scheme — the simplest way to partition. It takes the LAST
// element as the pivot and makes a single left-to-right pass, keeping a boundary
// between "seen values that are < pivot" and everything else. (The alternative,
// Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
// right. Lomuto is the one to memorize first.)
func partition(nums []int, lo, hi int) int {
    // Pivot = the last element. Any element works; picking the last one is
    // simplest, but on already-sorted input it causes the O(n^2) worst case —
    // production code often picks a random or median-of-three pivot instead.
    pivot := nums[hi]

    // i is the boundary of the "< pivot" region: everything in nums[lo..i) is
    // known to be smaller than the pivot. It starts empty (i == lo).
    i := lo

    // Scan every element before the pivot with j.
    for j := lo; j < hi; j++ {
        // Does nums[j] belong in the "< pivot" region? If so, swap it to the
        // boundary (position i), which places it just past the known-smaller run.
        if nums[j] < pivot {
            nums[i], nums[j] = nums[j], nums[i]

            // The region grew by one, so advance the boundary.
            i++
        }
    }

    // The scan is done: nums[lo..i) < pivot and nums[i..hi) >= pivot, so index i
    // is exactly where the pivot belongs. Swap it in from the end.
    nums[i], nums[hi] = nums[hi], nums[i]
    return i
}

# Sorts nums[lo..hi] in place. Call it as quick_sort(nums, 0, len(nums) - 1).
def quick_sort(nums, lo, hi):
    pass

# Sorts nums[lo..hi] in place. Call it as quick_sort(nums, 0, len(nums) - 1).
def quick_sort(nums, lo, hi):
    # Divide and conquer. Base case: a range of 0 or 1 element is already
    # sorted, so there's nothing to do.

# Sorts nums[lo..hi] in place. Call it as quick_sort(nums, 0, len(nums) - 1).
def quick_sort(nums, lo, hi):
    # Divide and conquer. Base case: a range of 0 or 1 element is already
    # sorted, so there's nothing to do.
    if lo >= hi:
        return

# Sorts nums[lo..hi] in place. Call it as quick_sort(nums, 0, len(nums) - 1).
def quick_sort(nums, lo, hi):
    # Divide and conquer. Base case: a range of 0 or 1 element is already
    # sorted, so there's nothing to do.
    if lo >= hi:
        return

    # Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
    # returning the index p the pivot lands on. Afterwards everything left of p
    # is < pivot, everything right is >= pivot, and the pivot sits in its final
    # sorted position.

# Sorts nums[lo..hi] in place. Call it as quick_sort(nums, 0, len(nums) - 1).
def quick_sort(nums, lo, hi):
    # Divide and conquer. Base case: a range of 0 or 1 element is already
    # sorted, so there's nothing to do.
    if lo >= hi:
        return

    # Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
    # returning the index p the pivot lands on. Afterwards everything left of p
    # is < pivot, everything right is >= pivot, and the pivot sits in its final
    # sorted position.
    p = partition(nums, lo, hi)

# Sorts nums[lo..hi] in place. Call it as quick_sort(nums, 0, len(nums) - 1).
def quick_sort(nums, lo, hi):
    # Divide and conquer. Base case: a range of 0 or 1 element is already
    # sorted, so there's nothing to do.
    if lo >= hi:
        return

    # Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
    # returning the index p the pivot lands on. Afterwards everything left of p
    # is < pivot, everything right is >= pivot, and the pivot sits in its final
    # sorted position.
    p = partition(nums, lo, hi)

    # The pivot at p is already correct, so recurse on the two sides only —
    # never on p itself. That shrinking range is what guarantees termination.

# Sorts nums[lo..hi] in place. Call it as quick_sort(nums, 0, len(nums) - 1).
def quick_sort(nums, lo, hi):
    # Divide and conquer. Base case: a range of 0 or 1 element is already
    # sorted, so there's nothing to do.
    if lo >= hi:
        return

    # Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
    # returning the index p the pivot lands on. Afterwards everything left of p
    # is < pivot, everything right is >= pivot, and the pivot sits in its final
    # sorted position.
    p = partition(nums, lo, hi)

    # The pivot at p is already correct, so recurse on the two sides only —
    # never on p itself. That shrinking range is what guarantees termination.
    quick_sort(nums, lo, p - 1)
    quick_sort(nums, p + 1, hi)

# Sorts nums[lo..hi] in place. Call it as quick_sort(nums, 0, len(nums) - 1).
def quick_sort(nums, lo, hi):
    # Divide and conquer. Base case: a range of 0 or 1 element is already
    # sorted, so there's nothing to do.
    if lo >= hi:
        return

    # Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
    # returning the index p the pivot lands on. Afterwards everything left of p
    # is < pivot, everything right is >= pivot, and the pivot sits in its final
    # sorted position.
    p = partition(nums, lo, hi)

    # The pivot at p is already correct, so recurse on the two sides only —
    # never on p itself. That shrinking range is what guarantees termination.
    quick_sort(nums, lo, p - 1)
    quick_sort(nums, p + 1, hi)

# Lomuto partition scheme — the simplest way to partition. It takes the LAST
# element as the pivot and makes a single left-to-right pass, keeping a boundary
# between "seen values that are < pivot" and everything else. (The alternative,
# Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
# right. Lomuto is the one to memorize first.)

# Sorts nums[lo..hi] in place. Call it as quick_sort(nums, 0, len(nums) - 1).
def quick_sort(nums, lo, hi):
    # Divide and conquer. Base case: a range of 0 or 1 element is already
    # sorted, so there's nothing to do.
    if lo >= hi:
        return

    # Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
    # returning the index p the pivot lands on. Afterwards everything left of p
    # is < pivot, everything right is >= pivot, and the pivot sits in its final
    # sorted position.
    p = partition(nums, lo, hi)

    # The pivot at p is already correct, so recurse on the two sides only —
    # never on p itself. That shrinking range is what guarantees termination.
    quick_sort(nums, lo, p - 1)
    quick_sort(nums, p + 1, hi)

# Lomuto partition scheme — the simplest way to partition. It takes the LAST
# element as the pivot and makes a single left-to-right pass, keeping a boundary
# between "seen values that are < pivot" and everything else. (The alternative,
# Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
# right. Lomuto is the one to memorize first.)
def partition(nums, lo, hi):

# Sorts nums[lo..hi] in place. Call it as quick_sort(nums, 0, len(nums) - 1).
def quick_sort(nums, lo, hi):
    # Divide and conquer. Base case: a range of 0 or 1 element is already
    # sorted, so there's nothing to do.
    if lo >= hi:
        return

    # Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
    # returning the index p the pivot lands on. Afterwards everything left of p
    # is < pivot, everything right is >= pivot, and the pivot sits in its final
    # sorted position.
    p = partition(nums, lo, hi)

    # The pivot at p is already correct, so recurse on the two sides only —
    # never on p itself. That shrinking range is what guarantees termination.
    quick_sort(nums, lo, p - 1)
    quick_sort(nums, p + 1, hi)

# Lomuto partition scheme — the simplest way to partition. It takes the LAST
# element as the pivot and makes a single left-to-right pass, keeping a boundary
# between "seen values that are < pivot" and everything else. (The alternative,
# Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
# right. Lomuto is the one to memorize first.)
def partition(nums, lo, hi):
    # Pivot = the last element. Any element works; picking the last one is
    # simplest, but on already-sorted input it causes the O(n^2) worst case —
    # production code often picks a random or median-of-three pivot instead.

# Sorts nums[lo..hi] in place. Call it as quick_sort(nums, 0, len(nums) - 1).
def quick_sort(nums, lo, hi):
    # Divide and conquer. Base case: a range of 0 or 1 element is already
    # sorted, so there's nothing to do.
    if lo >= hi:
        return

    # Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
    # returning the index p the pivot lands on. Afterwards everything left of p
    # is < pivot, everything right is >= pivot, and the pivot sits in its final
    # sorted position.
    p = partition(nums, lo, hi)

    # The pivot at p is already correct, so recurse on the two sides only —
    # never on p itself. That shrinking range is what guarantees termination.
    quick_sort(nums, lo, p - 1)
    quick_sort(nums, p + 1, hi)

# Lomuto partition scheme — the simplest way to partition. It takes the LAST
# element as the pivot and makes a single left-to-right pass, keeping a boundary
# between "seen values that are < pivot" and everything else. (The alternative,
# Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
# right. Lomuto is the one to memorize first.)
def partition(nums, lo, hi):
    # Pivot = the last element. Any element works; picking the last one is
    # simplest, but on already-sorted input it causes the O(n^2) worst case —
    # production code often picks a random or median-of-three pivot instead.
    pivot = nums[hi]

# Sorts nums[lo..hi] in place. Call it as quick_sort(nums, 0, len(nums) - 1).
def quick_sort(nums, lo, hi):
    # Divide and conquer. Base case: a range of 0 or 1 element is already
    # sorted, so there's nothing to do.
    if lo >= hi:
        return

    # Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
    # returning the index p the pivot lands on. Afterwards everything left of p
    # is < pivot, everything right is >= pivot, and the pivot sits in its final
    # sorted position.
    p = partition(nums, lo, hi)

    # The pivot at p is already correct, so recurse on the two sides only —
    # never on p itself. That shrinking range is what guarantees termination.
    quick_sort(nums, lo, p - 1)
    quick_sort(nums, p + 1, hi)

# Lomuto partition scheme — the simplest way to partition. It takes the LAST
# element as the pivot and makes a single left-to-right pass, keeping a boundary
# between "seen values that are < pivot" and everything else. (The alternative,
# Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
# right. Lomuto is the one to memorize first.)
def partition(nums, lo, hi):
    # Pivot = the last element. Any element works; picking the last one is
    # simplest, but on already-sorted input it causes the O(n^2) worst case —
    # production code often picks a random or median-of-three pivot instead.
    pivot = nums[hi]

    # i is the boundary of the "< pivot" region: everything in nums[lo..i) is
    # known to be smaller than the pivot. It starts empty (i == lo).

# Sorts nums[lo..hi] in place. Call it as quick_sort(nums, 0, len(nums) - 1).
def quick_sort(nums, lo, hi):
    # Divide and conquer. Base case: a range of 0 or 1 element is already
    # sorted, so there's nothing to do.
    if lo >= hi:
        return

    # Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
    # returning the index p the pivot lands on. Afterwards everything left of p
    # is < pivot, everything right is >= pivot, and the pivot sits in its final
    # sorted position.
    p = partition(nums, lo, hi)

    # The pivot at p is already correct, so recurse on the two sides only —
    # never on p itself. That shrinking range is what guarantees termination.
    quick_sort(nums, lo, p - 1)
    quick_sort(nums, p + 1, hi)

# Lomuto partition scheme — the simplest way to partition. It takes the LAST
# element as the pivot and makes a single left-to-right pass, keeping a boundary
# between "seen values that are < pivot" and everything else. (The alternative,
# Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
# right. Lomuto is the one to memorize first.)
def partition(nums, lo, hi):
    # Pivot = the last element. Any element works; picking the last one is
    # simplest, but on already-sorted input it causes the O(n^2) worst case —
    # production code often picks a random or median-of-three pivot instead.
    pivot = nums[hi]

    # i is the boundary of the "< pivot" region: everything in nums[lo..i) is
    # known to be smaller than the pivot. It starts empty (i == lo).
    i = lo

# Sorts nums[lo..hi] in place. Call it as quick_sort(nums, 0, len(nums) - 1).
def quick_sort(nums, lo, hi):
    # Divide and conquer. Base case: a range of 0 or 1 element is already
    # sorted, so there's nothing to do.
    if lo >= hi:
        return

    # Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
    # returning the index p the pivot lands on. Afterwards everything left of p
    # is < pivot, everything right is >= pivot, and the pivot sits in its final
    # sorted position.
    p = partition(nums, lo, hi)

    # The pivot at p is already correct, so recurse on the two sides only —
    # never on p itself. That shrinking range is what guarantees termination.
    quick_sort(nums, lo, p - 1)
    quick_sort(nums, p + 1, hi)

# Lomuto partition scheme — the simplest way to partition. It takes the LAST
# element as the pivot and makes a single left-to-right pass, keeping a boundary
# between "seen values that are < pivot" and everything else. (The alternative,
# Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
# right. Lomuto is the one to memorize first.)
def partition(nums, lo, hi):
    # Pivot = the last element. Any element works; picking the last one is
    # simplest, but on already-sorted input it causes the O(n^2) worst case —
    # production code often picks a random or median-of-three pivot instead.
    pivot = nums[hi]

    # i is the boundary of the "< pivot" region: everything in nums[lo..i) is
    # known to be smaller than the pivot. It starts empty (i == lo).
    i = lo

    # Scan every element before the pivot with j.

# Sorts nums[lo..hi] in place. Call it as quick_sort(nums, 0, len(nums) - 1).
def quick_sort(nums, lo, hi):
    # Divide and conquer. Base case: a range of 0 or 1 element is already
    # sorted, so there's nothing to do.
    if lo >= hi:
        return

    # Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
    # returning the index p the pivot lands on. Afterwards everything left of p
    # is < pivot, everything right is >= pivot, and the pivot sits in its final
    # sorted position.
    p = partition(nums, lo, hi)

    # The pivot at p is already correct, so recurse on the two sides only —
    # never on p itself. That shrinking range is what guarantees termination.
    quick_sort(nums, lo, p - 1)
    quick_sort(nums, p + 1, hi)

# Lomuto partition scheme — the simplest way to partition. It takes the LAST
# element as the pivot and makes a single left-to-right pass, keeping a boundary
# between "seen values that are < pivot" and everything else. (The alternative,
# Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
# right. Lomuto is the one to memorize first.)
def partition(nums, lo, hi):
    # Pivot = the last element. Any element works; picking the last one is
    # simplest, but on already-sorted input it causes the O(n^2) worst case —
    # production code often picks a random or median-of-three pivot instead.
    pivot = nums[hi]

    # i is the boundary of the "< pivot" region: everything in nums[lo..i) is
    # known to be smaller than the pivot. It starts empty (i == lo).
    i = lo

    # Scan every element before the pivot with j.
    for j in range(lo, hi):

# Sorts nums[lo..hi] in place. Call it as quick_sort(nums, 0, len(nums) - 1).
def quick_sort(nums, lo, hi):
    # Divide and conquer. Base case: a range of 0 or 1 element is already
    # sorted, so there's nothing to do.
    if lo >= hi:
        return

    # Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
    # returning the index p the pivot lands on. Afterwards everything left of p
    # is < pivot, everything right is >= pivot, and the pivot sits in its final
    # sorted position.
    p = partition(nums, lo, hi)

    # The pivot at p is already correct, so recurse on the two sides only —
    # never on p itself. That shrinking range is what guarantees termination.
    quick_sort(nums, lo, p - 1)
    quick_sort(nums, p + 1, hi)

# Lomuto partition scheme — the simplest way to partition. It takes the LAST
# element as the pivot and makes a single left-to-right pass, keeping a boundary
# between "seen values that are < pivot" and everything else. (The alternative,
# Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
# right. Lomuto is the one to memorize first.)
def partition(nums, lo, hi):
    # Pivot = the last element. Any element works; picking the last one is
    # simplest, but on already-sorted input it causes the O(n^2) worst case —
    # production code often picks a random or median-of-three pivot instead.
    pivot = nums[hi]

    # i is the boundary of the "< pivot" region: everything in nums[lo..i) is
    # known to be smaller than the pivot. It starts empty (i == lo).
    i = lo

    # Scan every element before the pivot with j.
    for j in range(lo, hi):
        # Does nums[j] belong in the "< pivot" region? If so, swap it to the
        # boundary (position i), which places it just past the known-smaller run.

            # The region grew by one, so advance the boundary.

# Sorts nums[lo..hi] in place. Call it as quick_sort(nums, 0, len(nums) - 1).
def quick_sort(nums, lo, hi):
    # Divide and conquer. Base case: a range of 0 or 1 element is already
    # sorted, so there's nothing to do.
    if lo >= hi:
        return

    # Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
    # returning the index p the pivot lands on. Afterwards everything left of p
    # is < pivot, everything right is >= pivot, and the pivot sits in its final
    # sorted position.
    p = partition(nums, lo, hi)

    # The pivot at p is already correct, so recurse on the two sides only —
    # never on p itself. That shrinking range is what guarantees termination.
    quick_sort(nums, lo, p - 1)
    quick_sort(nums, p + 1, hi)

# Lomuto partition scheme — the simplest way to partition. It takes the LAST
# element as the pivot and makes a single left-to-right pass, keeping a boundary
# between "seen values that are < pivot" and everything else. (The alternative,
# Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
# right. Lomuto is the one to memorize first.)
def partition(nums, lo, hi):
    # Pivot = the last element. Any element works; picking the last one is
    # simplest, but on already-sorted input it causes the O(n^2) worst case —
    # production code often picks a random or median-of-three pivot instead.
    pivot = nums[hi]

    # i is the boundary of the "< pivot" region: everything in nums[lo..i) is
    # known to be smaller than the pivot. It starts empty (i == lo).
    i = lo

    # Scan every element before the pivot with j.
    for j in range(lo, hi):
        # Does nums[j] belong in the "< pivot" region? If so, swap it to the
        # boundary (position i), which places it just past the known-smaller run.
        if nums[j] < pivot:
            nums[i], nums[j] = nums[j], nums[i]

            # The region grew by one, so advance the boundary.
            i += 1

# Sorts nums[lo..hi] in place. Call it as quick_sort(nums, 0, len(nums) - 1).
def quick_sort(nums, lo, hi):
    # Divide and conquer. Base case: a range of 0 or 1 element is already
    # sorted, so there's nothing to do.
    if lo >= hi:
        return

    # Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
    # returning the index p the pivot lands on. Afterwards everything left of p
    # is < pivot, everything right is >= pivot, and the pivot sits in its final
    # sorted position.
    p = partition(nums, lo, hi)

    # The pivot at p is already correct, so recurse on the two sides only —
    # never on p itself. That shrinking range is what guarantees termination.
    quick_sort(nums, lo, p - 1)
    quick_sort(nums, p + 1, hi)

# Lomuto partition scheme — the simplest way to partition. It takes the LAST
# element as the pivot and makes a single left-to-right pass, keeping a boundary
# between "seen values that are < pivot" and everything else. (The alternative,
# Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
# right. Lomuto is the one to memorize first.)
def partition(nums, lo, hi):
    # Pivot = the last element. Any element works; picking the last one is
    # simplest, but on already-sorted input it causes the O(n^2) worst case —
    # production code often picks a random or median-of-three pivot instead.
    pivot = nums[hi]

    # i is the boundary of the "< pivot" region: everything in nums[lo..i) is
    # known to be smaller than the pivot. It starts empty (i == lo).
    i = lo

    # Scan every element before the pivot with j.
    for j in range(lo, hi):
        # Does nums[j] belong in the "< pivot" region? If so, swap it to the
        # boundary (position i), which places it just past the known-smaller run.
        if nums[j] < pivot:
            nums[i], nums[j] = nums[j], nums[i]

            # The region grew by one, so advance the boundary.
            i += 1

    # The scan is done: nums[lo..i) < pivot and nums[i..hi) >= pivot, so index i
    # is exactly where the pivot belongs. Swap it in from the end.

# Sorts nums[lo..hi] in place. Call it as quick_sort(nums, 0, len(nums) - 1).
def quick_sort(nums, lo, hi):
    # Divide and conquer. Base case: a range of 0 or 1 element is already
    # sorted, so there's nothing to do.
    if lo >= hi:
        return

    # Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
    # returning the index p the pivot lands on. Afterwards everything left of p
    # is < pivot, everything right is >= pivot, and the pivot sits in its final
    # sorted position.
    p = partition(nums, lo, hi)

    # The pivot at p is already correct, so recurse on the two sides only —
    # never on p itself. That shrinking range is what guarantees termination.
    quick_sort(nums, lo, p - 1)
    quick_sort(nums, p + 1, hi)

# Lomuto partition scheme — the simplest way to partition. It takes the LAST
# element as the pivot and makes a single left-to-right pass, keeping a boundary
# between "seen values that are < pivot" and everything else. (The alternative,
# Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
# right. Lomuto is the one to memorize first.)
def partition(nums, lo, hi):
    # Pivot = the last element. Any element works; picking the last one is
    # simplest, but on already-sorted input it causes the O(n^2) worst case —
    # production code often picks a random or median-of-three pivot instead.
    pivot = nums[hi]

    # i is the boundary of the "< pivot" region: everything in nums[lo..i) is
    # known to be smaller than the pivot. It starts empty (i == lo).
    i = lo

    # Scan every element before the pivot with j.
    for j in range(lo, hi):
        # Does nums[j] belong in the "< pivot" region? If so, swap it to the
        # boundary (position i), which places it just past the known-smaller run.
        if nums[j] < pivot:
            nums[i], nums[j] = nums[j], nums[i]

            # The region grew by one, so advance the boundary.
            i += 1

    # The scan is done: nums[lo..i) < pivot and nums[i..hi) >= pivot, so index i
    # is exactly where the pivot belongs. Swap it in from the end.
    nums[i], nums[hi] = nums[hi], nums[i]
    return i

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, nums.length - 1).
function quickSort(nums, lo, hi) {
  
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, nums.length - 1).
function quickSort(nums, lo, hi) {
  // Divide and conquer. Base case: a range of 0 or 1 element is already
  // sorted, so there's nothing to do.
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, nums.length - 1).
function quickSort(nums, lo, hi) {
  // Divide and conquer. Base case: a range of 0 or 1 element is already
  // sorted, so there's nothing to do.
  if (lo >= hi) {
    return;
  }
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, nums.length - 1).
function quickSort(nums, lo, hi) {
  // Divide and conquer. Base case: a range of 0 or 1 element is already
  // sorted, so there's nothing to do.
  if (lo >= hi) {
    return;
  }

  // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
  // returning the index p the pivot lands on. Afterwards everything left of p
  // is < pivot, everything right is >= pivot, and the pivot sits in its final
  // sorted position.
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, nums.length - 1).
function quickSort(nums, lo, hi) {
  // Divide and conquer. Base case: a range of 0 or 1 element is already
  // sorted, so there's nothing to do.
  if (lo >= hi) {
    return;
  }

  // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
  // returning the index p the pivot lands on. Afterwards everything left of p
  // is < pivot, everything right is >= pivot, and the pivot sits in its final
  // sorted position.
  const p = partition(nums, lo, hi);
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, nums.length - 1).
function quickSort(nums, lo, hi) {
  // Divide and conquer. Base case: a range of 0 or 1 element is already
  // sorted, so there's nothing to do.
  if (lo >= hi) {
    return;
  }

  // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
  // returning the index p the pivot lands on. Afterwards everything left of p
  // is < pivot, everything right is >= pivot, and the pivot sits in its final
  // sorted position.
  const p = partition(nums, lo, hi);

  // The pivot at p is already correct, so recurse on the two sides only —
  // never on p itself. That shrinking range is what guarantees termination.
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, nums.length - 1).
function quickSort(nums, lo, hi) {
  // Divide and conquer. Base case: a range of 0 or 1 element is already
  // sorted, so there's nothing to do.
  if (lo >= hi) {
    return;
  }

  // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
  // returning the index p the pivot lands on. Afterwards everything left of p
  // is < pivot, everything right is >= pivot, and the pivot sits in its final
  // sorted position.
  const p = partition(nums, lo, hi);

  // The pivot at p is already correct, so recurse on the two sides only —
  // never on p itself. That shrinking range is what guarantees termination.
  quickSort(nums, lo, p - 1);
  quickSort(nums, p + 1, hi);
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, nums.length - 1).
function quickSort(nums, lo, hi) {
  // Divide and conquer. Base case: a range of 0 or 1 element is already
  // sorted, so there's nothing to do.
  if (lo >= hi) {
    return;
  }

  // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
  // returning the index p the pivot lands on. Afterwards everything left of p
  // is < pivot, everything right is >= pivot, and the pivot sits in its final
  // sorted position.
  const p = partition(nums, lo, hi);

  // The pivot at p is already correct, so recurse on the two sides only —
  // never on p itself. That shrinking range is what guarantees termination.
  quickSort(nums, lo, p - 1);
  quickSort(nums, p + 1, hi);
}

// Lomuto partition scheme — the simplest way to partition. It takes the LAST
// element as the pivot and makes a single left-to-right pass, keeping a boundary
// between "seen values that are < pivot" and everything else. (The alternative,
// Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
// right. Lomuto is the one to memorize first.)

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, nums.length - 1).
function quickSort(nums, lo, hi) {
  // Divide and conquer. Base case: a range of 0 or 1 element is already
  // sorted, so there's nothing to do.
  if (lo >= hi) {
    return;
  }

  // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
  // returning the index p the pivot lands on. Afterwards everything left of p
  // is < pivot, everything right is >= pivot, and the pivot sits in its final
  // sorted position.
  const p = partition(nums, lo, hi);

  // The pivot at p is already correct, so recurse on the two sides only —
  // never on p itself. That shrinking range is what guarantees termination.
  quickSort(nums, lo, p - 1);
  quickSort(nums, p + 1, hi);
}

// Lomuto partition scheme — the simplest way to partition. It takes the LAST
// element as the pivot and makes a single left-to-right pass, keeping a boundary
// between "seen values that are < pivot" and everything else. (The alternative,
// Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
// right. Lomuto is the one to memorize first.)
function partition(nums, lo, hi) {
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, nums.length - 1).
function quickSort(nums, lo, hi) {
  // Divide and conquer. Base case: a range of 0 or 1 element is already
  // sorted, so there's nothing to do.
  if (lo >= hi) {
    return;
  }

  // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
  // returning the index p the pivot lands on. Afterwards everything left of p
  // is < pivot, everything right is >= pivot, and the pivot sits in its final
  // sorted position.
  const p = partition(nums, lo, hi);

  // The pivot at p is already correct, so recurse on the two sides only —
  // never on p itself. That shrinking range is what guarantees termination.
  quickSort(nums, lo, p - 1);
  quickSort(nums, p + 1, hi);
}

// Lomuto partition scheme — the simplest way to partition. It takes the LAST
// element as the pivot and makes a single left-to-right pass, keeping a boundary
// between "seen values that are < pivot" and everything else. (The alternative,
// Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
// right. Lomuto is the one to memorize first.)
function partition(nums, lo, hi) {
  // Pivot = the last element. Any element works; picking the last one is
  // simplest, but on already-sorted input it causes the O(n^2) worst case —
  // production code often picks a random or median-of-three pivot instead.
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, nums.length - 1).
function quickSort(nums, lo, hi) {
  // Divide and conquer. Base case: a range of 0 or 1 element is already
  // sorted, so there's nothing to do.
  if (lo >= hi) {
    return;
  }

  // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
  // returning the index p the pivot lands on. Afterwards everything left of p
  // is < pivot, everything right is >= pivot, and the pivot sits in its final
  // sorted position.
  const p = partition(nums, lo, hi);

  // The pivot at p is already correct, so recurse on the two sides only —
  // never on p itself. That shrinking range is what guarantees termination.
  quickSort(nums, lo, p - 1);
  quickSort(nums, p + 1, hi);
}

// Lomuto partition scheme — the simplest way to partition. It takes the LAST
// element as the pivot and makes a single left-to-right pass, keeping a boundary
// between "seen values that are < pivot" and everything else. (The alternative,
// Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
// right. Lomuto is the one to memorize first.)
function partition(nums, lo, hi) {
  // Pivot = the last element. Any element works; picking the last one is
  // simplest, but on already-sorted input it causes the O(n^2) worst case —
  // production code often picks a random or median-of-three pivot instead.
  const pivot = nums[hi];
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, nums.length - 1).
function quickSort(nums, lo, hi) {
  // Divide and conquer. Base case: a range of 0 or 1 element is already
  // sorted, so there's nothing to do.
  if (lo >= hi) {
    return;
  }

  // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
  // returning the index p the pivot lands on. Afterwards everything left of p
  // is < pivot, everything right is >= pivot, and the pivot sits in its final
  // sorted position.
  const p = partition(nums, lo, hi);

  // The pivot at p is already correct, so recurse on the two sides only —
  // never on p itself. That shrinking range is what guarantees termination.
  quickSort(nums, lo, p - 1);
  quickSort(nums, p + 1, hi);
}

// Lomuto partition scheme — the simplest way to partition. It takes the LAST
// element as the pivot and makes a single left-to-right pass, keeping a boundary
// between "seen values that are < pivot" and everything else. (The alternative,
// Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
// right. Lomuto is the one to memorize first.)
function partition(nums, lo, hi) {
  // Pivot = the last element. Any element works; picking the last one is
  // simplest, but on already-sorted input it causes the O(n^2) worst case —
  // production code often picks a random or median-of-three pivot instead.
  const pivot = nums[hi];

  // i is the boundary of the "< pivot" region: everything in nums[lo..i) is
  // known to be smaller than the pivot. It starts empty (i == lo).
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, nums.length - 1).
function quickSort(nums, lo, hi) {
  // Divide and conquer. Base case: a range of 0 or 1 element is already
  // sorted, so there's nothing to do.
  if (lo >= hi) {
    return;
  }

  // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
  // returning the index p the pivot lands on. Afterwards everything left of p
  // is < pivot, everything right is >= pivot, and the pivot sits in its final
  // sorted position.
  const p = partition(nums, lo, hi);

  // The pivot at p is already correct, so recurse on the two sides only —
  // never on p itself. That shrinking range is what guarantees termination.
  quickSort(nums, lo, p - 1);
  quickSort(nums, p + 1, hi);
}

// Lomuto partition scheme — the simplest way to partition. It takes the LAST
// element as the pivot and makes a single left-to-right pass, keeping a boundary
// between "seen values that are < pivot" and everything else. (The alternative,
// Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
// right. Lomuto is the one to memorize first.)
function partition(nums, lo, hi) {
  // Pivot = the last element. Any element works; picking the last one is
  // simplest, but on already-sorted input it causes the O(n^2) worst case —
  // production code often picks a random or median-of-three pivot instead.
  const pivot = nums[hi];

  // i is the boundary of the "< pivot" region: everything in nums[lo..i) is
  // known to be smaller than the pivot. It starts empty (i == lo).
  let i = lo;
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, nums.length - 1).
function quickSort(nums, lo, hi) {
  // Divide and conquer. Base case: a range of 0 or 1 element is already
  // sorted, so there's nothing to do.
  if (lo >= hi) {
    return;
  }

  // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
  // returning the index p the pivot lands on. Afterwards everything left of p
  // is < pivot, everything right is >= pivot, and the pivot sits in its final
  // sorted position.
  const p = partition(nums, lo, hi);

  // The pivot at p is already correct, so recurse on the two sides only —
  // never on p itself. That shrinking range is what guarantees termination.
  quickSort(nums, lo, p - 1);
  quickSort(nums, p + 1, hi);
}

// Lomuto partition scheme — the simplest way to partition. It takes the LAST
// element as the pivot and makes a single left-to-right pass, keeping a boundary
// between "seen values that are < pivot" and everything else. (The alternative,
// Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
// right. Lomuto is the one to memorize first.)
function partition(nums, lo, hi) {
  // Pivot = the last element. Any element works; picking the last one is
  // simplest, but on already-sorted input it causes the O(n^2) worst case —
  // production code often picks a random or median-of-three pivot instead.
  const pivot = nums[hi];

  // i is the boundary of the "< pivot" region: everything in nums[lo..i) is
  // known to be smaller than the pivot. It starts empty (i == lo).
  let i = lo;

  // Scan every element before the pivot with j.
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, nums.length - 1).
function quickSort(nums, lo, hi) {
  // Divide and conquer. Base case: a range of 0 or 1 element is already
  // sorted, so there's nothing to do.
  if (lo >= hi) {
    return;
  }

  // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
  // returning the index p the pivot lands on. Afterwards everything left of p
  // is < pivot, everything right is >= pivot, and the pivot sits in its final
  // sorted position.
  const p = partition(nums, lo, hi);

  // The pivot at p is already correct, so recurse on the two sides only —
  // never on p itself. That shrinking range is what guarantees termination.
  quickSort(nums, lo, p - 1);
  quickSort(nums, p + 1, hi);
}

// Lomuto partition scheme — the simplest way to partition. It takes the LAST
// element as the pivot and makes a single left-to-right pass, keeping a boundary
// between "seen values that are < pivot" and everything else. (The alternative,
// Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
// right. Lomuto is the one to memorize first.)
function partition(nums, lo, hi) {
  // Pivot = the last element. Any element works; picking the last one is
  // simplest, but on already-sorted input it causes the O(n^2) worst case —
  // production code often picks a random or median-of-three pivot instead.
  const pivot = nums[hi];

  // i is the boundary of the "< pivot" region: everything in nums[lo..i) is
  // known to be smaller than the pivot. It starts empty (i == lo).
  let i = lo;

  // Scan every element before the pivot with j.
  for (let j = lo; j < hi; j++) {
  }
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, nums.length - 1).
function quickSort(nums, lo, hi) {
  // Divide and conquer. Base case: a range of 0 or 1 element is already
  // sorted, so there's nothing to do.
  if (lo >= hi) {
    return;
  }

  // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
  // returning the index p the pivot lands on. Afterwards everything left of p
  // is < pivot, everything right is >= pivot, and the pivot sits in its final
  // sorted position.
  const p = partition(nums, lo, hi);

  // The pivot at p is already correct, so recurse on the two sides only —
  // never on p itself. That shrinking range is what guarantees termination.
  quickSort(nums, lo, p - 1);
  quickSort(nums, p + 1, hi);
}

// Lomuto partition scheme — the simplest way to partition. It takes the LAST
// element as the pivot and makes a single left-to-right pass, keeping a boundary
// between "seen values that are < pivot" and everything else. (The alternative,
// Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
// right. Lomuto is the one to memorize first.)
function partition(nums, lo, hi) {
  // Pivot = the last element. Any element works; picking the last one is
  // simplest, but on already-sorted input it causes the O(n^2) worst case —
  // production code often picks a random or median-of-three pivot instead.
  const pivot = nums[hi];

  // i is the boundary of the "< pivot" region: everything in nums[lo..i) is
  // known to be smaller than the pivot. It starts empty (i == lo).
  let i = lo;

  // Scan every element before the pivot with j.
  for (let j = lo; j < hi; j++) {
    // Does nums[j] belong in the "< pivot" region? If so, swap it to the
    // boundary (position i), which places it just past the known-smaller run.

      // The region grew by one, so advance the boundary.
  }
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, nums.length - 1).
function quickSort(nums, lo, hi) {
  // Divide and conquer. Base case: a range of 0 or 1 element is already
  // sorted, so there's nothing to do.
  if (lo >= hi) {
    return;
  }

  // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
  // returning the index p the pivot lands on. Afterwards everything left of p
  // is < pivot, everything right is >= pivot, and the pivot sits in its final
  // sorted position.
  const p = partition(nums, lo, hi);

  // The pivot at p is already correct, so recurse on the two sides only —
  // never on p itself. That shrinking range is what guarantees termination.
  quickSort(nums, lo, p - 1);
  quickSort(nums, p + 1, hi);
}

// Lomuto partition scheme — the simplest way to partition. It takes the LAST
// element as the pivot and makes a single left-to-right pass, keeping a boundary
// between "seen values that are < pivot" and everything else. (The alternative,
// Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
// right. Lomuto is the one to memorize first.)
function partition(nums, lo, hi) {
  // Pivot = the last element. Any element works; picking the last one is
  // simplest, but on already-sorted input it causes the O(n^2) worst case —
  // production code often picks a random or median-of-three pivot instead.
  const pivot = nums[hi];

  // i is the boundary of the "< pivot" region: everything in nums[lo..i) is
  // known to be smaller than the pivot. It starts empty (i == lo).
  let i = lo;

  // Scan every element before the pivot with j.
  for (let j = lo; j < hi; j++) {
    // Does nums[j] belong in the "< pivot" region? If so, swap it to the
    // boundary (position i), which places it just past the known-smaller run.
    if (nums[j] < pivot) {
      [nums[i], nums[j]] = [nums[j], nums[i]];

      // The region grew by one, so advance the boundary.
      i++;
    }
  }
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, nums.length - 1).
function quickSort(nums, lo, hi) {
  // Divide and conquer. Base case: a range of 0 or 1 element is already
  // sorted, so there's nothing to do.
  if (lo >= hi) {
    return;
  }

  // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
  // returning the index p the pivot lands on. Afterwards everything left of p
  // is < pivot, everything right is >= pivot, and the pivot sits in its final
  // sorted position.
  const p = partition(nums, lo, hi);

  // The pivot at p is already correct, so recurse on the two sides only —
  // never on p itself. That shrinking range is what guarantees termination.
  quickSort(nums, lo, p - 1);
  quickSort(nums, p + 1, hi);
}

// Lomuto partition scheme — the simplest way to partition. It takes the LAST
// element as the pivot and makes a single left-to-right pass, keeping a boundary
// between "seen values that are < pivot" and everything else. (The alternative,
// Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
// right. Lomuto is the one to memorize first.)
function partition(nums, lo, hi) {
  // Pivot = the last element. Any element works; picking the last one is
  // simplest, but on already-sorted input it causes the O(n^2) worst case —
  // production code often picks a random or median-of-three pivot instead.
  const pivot = nums[hi];

  // i is the boundary of the "< pivot" region: everything in nums[lo..i) is
  // known to be smaller than the pivot. It starts empty (i == lo).
  let i = lo;

  // Scan every element before the pivot with j.
  for (let j = lo; j < hi; j++) {
    // Does nums[j] belong in the "< pivot" region? If so, swap it to the
    // boundary (position i), which places it just past the known-smaller run.
    if (nums[j] < pivot) {
      [nums[i], nums[j]] = [nums[j], nums[i]];

      // The region grew by one, so advance the boundary.
      i++;
    }
  }

  // The scan is done: nums[lo..i) < pivot and nums[i..hi) >= pivot, so index i
  // is exactly where the pivot belongs. Swap it in from the end.
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, nums.length - 1).
function quickSort(nums, lo, hi) {
  // Divide and conquer. Base case: a range of 0 or 1 element is already
  // sorted, so there's nothing to do.
  if (lo >= hi) {
    return;
  }

  // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
  // returning the index p the pivot lands on. Afterwards everything left of p
  // is < pivot, everything right is >= pivot, and the pivot sits in its final
  // sorted position.
  const p = partition(nums, lo, hi);

  // The pivot at p is already correct, so recurse on the two sides only —
  // never on p itself. That shrinking range is what guarantees termination.
  quickSort(nums, lo, p - 1);
  quickSort(nums, p + 1, hi);
}

// Lomuto partition scheme — the simplest way to partition. It takes the LAST
// element as the pivot and makes a single left-to-right pass, keeping a boundary
// between "seen values that are < pivot" and everything else. (The alternative,
// Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
// right. Lomuto is the one to memorize first.)
function partition(nums, lo, hi) {
  // Pivot = the last element. Any element works; picking the last one is
  // simplest, but on already-sorted input it causes the O(n^2) worst case —
  // production code often picks a random or median-of-three pivot instead.
  const pivot = nums[hi];

  // i is the boundary of the "< pivot" region: everything in nums[lo..i) is
  // known to be smaller than the pivot. It starts empty (i == lo).
  let i = lo;

  // Scan every element before the pivot with j.
  for (let j = lo; j < hi; j++) {
    // Does nums[j] belong in the "< pivot" region? If so, swap it to the
    // boundary (position i), which places it just past the known-smaller run.
    if (nums[j] < pivot) {
      [nums[i], nums[j]] = [nums[j], nums[i]];

      // The region grew by one, so advance the boundary.
      i++;
    }
  }

  // The scan is done: nums[lo..i) < pivot and nums[i..hi) >= pivot, so index i
  // is exactly where the pivot belongs. Swap it in from the end.
  [nums[i], nums[hi]] = [nums[hi], nums[i]];
  return i;
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, nums.length - 1).
function quickSort(nums: number[], lo: number, hi: number): void {
  
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, nums.length - 1).
function quickSort(nums: number[], lo: number, hi: number): void {
  // Divide and conquer. Base case: a range of 0 or 1 element is already
  // sorted, so there's nothing to do.
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, nums.length - 1).
function quickSort(nums: number[], lo: number, hi: number): void {
  // Divide and conquer. Base case: a range of 0 or 1 element is already
  // sorted, so there's nothing to do.
  if (lo >= hi) {
    return;
  }
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, nums.length - 1).
function quickSort(nums: number[], lo: number, hi: number): void {
  // Divide and conquer. Base case: a range of 0 or 1 element is already
  // sorted, so there's nothing to do.
  if (lo >= hi) {
    return;
  }

  // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
  // returning the index p the pivot lands on. Afterwards everything left of p
  // is < pivot, everything right is >= pivot, and the pivot sits in its final
  // sorted position.
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, nums.length - 1).
function quickSort(nums: number[], lo: number, hi: number): void {
  // Divide and conquer. Base case: a range of 0 or 1 element is already
  // sorted, so there's nothing to do.
  if (lo >= hi) {
    return;
  }

  // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
  // returning the index p the pivot lands on. Afterwards everything left of p
  // is < pivot, everything right is >= pivot, and the pivot sits in its final
  // sorted position.
  const p = partition(nums, lo, hi);
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, nums.length - 1).
function quickSort(nums: number[], lo: number, hi: number): void {
  // Divide and conquer. Base case: a range of 0 or 1 element is already
  // sorted, so there's nothing to do.
  if (lo >= hi) {
    return;
  }

  // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
  // returning the index p the pivot lands on. Afterwards everything left of p
  // is < pivot, everything right is >= pivot, and the pivot sits in its final
  // sorted position.
  const p = partition(nums, lo, hi);

  // The pivot at p is already correct, so recurse on the two sides only —
  // never on p itself. That shrinking range is what guarantees termination.
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, nums.length - 1).
function quickSort(nums: number[], lo: number, hi: number): void {
  // Divide and conquer. Base case: a range of 0 or 1 element is already
  // sorted, so there's nothing to do.
  if (lo >= hi) {
    return;
  }

  // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
  // returning the index p the pivot lands on. Afterwards everything left of p
  // is < pivot, everything right is >= pivot, and the pivot sits in its final
  // sorted position.
  const p = partition(nums, lo, hi);

  // The pivot at p is already correct, so recurse on the two sides only —
  // never on p itself. That shrinking range is what guarantees termination.
  quickSort(nums, lo, p - 1);
  quickSort(nums, p + 1, hi);
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, nums.length - 1).
function quickSort(nums: number[], lo: number, hi: number): void {
  // Divide and conquer. Base case: a range of 0 or 1 element is already
  // sorted, so there's nothing to do.
  if (lo >= hi) {
    return;
  }

  // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
  // returning the index p the pivot lands on. Afterwards everything left of p
  // is < pivot, everything right is >= pivot, and the pivot sits in its final
  // sorted position.
  const p = partition(nums, lo, hi);

  // The pivot at p is already correct, so recurse on the two sides only —
  // never on p itself. That shrinking range is what guarantees termination.
  quickSort(nums, lo, p - 1);
  quickSort(nums, p + 1, hi);
}

// Lomuto partition scheme — the simplest way to partition. It takes the LAST
// element as the pivot and makes a single left-to-right pass, keeping a boundary
// between "seen values that are < pivot" and everything else. (The alternative,
// Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
// right. Lomuto is the one to memorize first.)

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, nums.length - 1).
function quickSort(nums: number[], lo: number, hi: number): void {
  // Divide and conquer. Base case: a range of 0 or 1 element is already
  // sorted, so there's nothing to do.
  if (lo >= hi) {
    return;
  }

  // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
  // returning the index p the pivot lands on. Afterwards everything left of p
  // is < pivot, everything right is >= pivot, and the pivot sits in its final
  // sorted position.
  const p = partition(nums, lo, hi);

  // The pivot at p is already correct, so recurse on the two sides only —
  // never on p itself. That shrinking range is what guarantees termination.
  quickSort(nums, lo, p - 1);
  quickSort(nums, p + 1, hi);
}

// Lomuto partition scheme — the simplest way to partition. It takes the LAST
// element as the pivot and makes a single left-to-right pass, keeping a boundary
// between "seen values that are < pivot" and everything else. (The alternative,
// Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
// right. Lomuto is the one to memorize first.)
function partition(nums: number[], lo: number, hi: number): number {
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, nums.length - 1).
function quickSort(nums: number[], lo: number, hi: number): void {
  // Divide and conquer. Base case: a range of 0 or 1 element is already
  // sorted, so there's nothing to do.
  if (lo >= hi) {
    return;
  }

  // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
  // returning the index p the pivot lands on. Afterwards everything left of p
  // is < pivot, everything right is >= pivot, and the pivot sits in its final
  // sorted position.
  const p = partition(nums, lo, hi);

  // The pivot at p is already correct, so recurse on the two sides only —
  // never on p itself. That shrinking range is what guarantees termination.
  quickSort(nums, lo, p - 1);
  quickSort(nums, p + 1, hi);
}

// Lomuto partition scheme — the simplest way to partition. It takes the LAST
// element as the pivot and makes a single left-to-right pass, keeping a boundary
// between "seen values that are < pivot" and everything else. (The alternative,
// Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
// right. Lomuto is the one to memorize first.)
function partition(nums: number[], lo: number, hi: number): number {
  // Pivot = the last element. Any element works; picking the last one is
  // simplest, but on already-sorted input it causes the O(n^2) worst case —
  // production code often picks a random or median-of-three pivot instead.
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, nums.length - 1).
function quickSort(nums: number[], lo: number, hi: number): void {
  // Divide and conquer. Base case: a range of 0 or 1 element is already
  // sorted, so there's nothing to do.
  if (lo >= hi) {
    return;
  }

  // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
  // returning the index p the pivot lands on. Afterwards everything left of p
  // is < pivot, everything right is >= pivot, and the pivot sits in its final
  // sorted position.
  const p = partition(nums, lo, hi);

  // The pivot at p is already correct, so recurse on the two sides only —
  // never on p itself. That shrinking range is what guarantees termination.
  quickSort(nums, lo, p - 1);
  quickSort(nums, p + 1, hi);
}

// Lomuto partition scheme — the simplest way to partition. It takes the LAST
// element as the pivot and makes a single left-to-right pass, keeping a boundary
// between "seen values that are < pivot" and everything else. (The alternative,
// Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
// right. Lomuto is the one to memorize first.)
function partition(nums: number[], lo: number, hi: number): number {
  // Pivot = the last element. Any element works; picking the last one is
  // simplest, but on already-sorted input it causes the O(n^2) worst case —
  // production code often picks a random or median-of-three pivot instead.
  const pivot = nums[hi];
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, nums.length - 1).
function quickSort(nums: number[], lo: number, hi: number): void {
  // Divide and conquer. Base case: a range of 0 or 1 element is already
  // sorted, so there's nothing to do.
  if (lo >= hi) {
    return;
  }

  // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
  // returning the index p the pivot lands on. Afterwards everything left of p
  // is < pivot, everything right is >= pivot, and the pivot sits in its final
  // sorted position.
  const p = partition(nums, lo, hi);

  // The pivot at p is already correct, so recurse on the two sides only —
  // never on p itself. That shrinking range is what guarantees termination.
  quickSort(nums, lo, p - 1);
  quickSort(nums, p + 1, hi);
}

// Lomuto partition scheme — the simplest way to partition. It takes the LAST
// element as the pivot and makes a single left-to-right pass, keeping a boundary
// between "seen values that are < pivot" and everything else. (The alternative,
// Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
// right. Lomuto is the one to memorize first.)
function partition(nums: number[], lo: number, hi: number): number {
  // Pivot = the last element. Any element works; picking the last one is
  // simplest, but on already-sorted input it causes the O(n^2) worst case —
  // production code often picks a random or median-of-three pivot instead.
  const pivot = nums[hi];

  // i is the boundary of the "< pivot" region: everything in nums[lo..i) is
  // known to be smaller than the pivot. It starts empty (i == lo).
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, nums.length - 1).
function quickSort(nums: number[], lo: number, hi: number): void {
  // Divide and conquer. Base case: a range of 0 or 1 element is already
  // sorted, so there's nothing to do.
  if (lo >= hi) {
    return;
  }

  // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
  // returning the index p the pivot lands on. Afterwards everything left of p
  // is < pivot, everything right is >= pivot, and the pivot sits in its final
  // sorted position.
  const p = partition(nums, lo, hi);

  // The pivot at p is already correct, so recurse on the two sides only —
  // never on p itself. That shrinking range is what guarantees termination.
  quickSort(nums, lo, p - 1);
  quickSort(nums, p + 1, hi);
}

// Lomuto partition scheme — the simplest way to partition. It takes the LAST
// element as the pivot and makes a single left-to-right pass, keeping a boundary
// between "seen values that are < pivot" and everything else. (The alternative,
// Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
// right. Lomuto is the one to memorize first.)
function partition(nums: number[], lo: number, hi: number): number {
  // Pivot = the last element. Any element works; picking the last one is
  // simplest, but on already-sorted input it causes the O(n^2) worst case —
  // production code often picks a random or median-of-three pivot instead.
  const pivot = nums[hi];

  // i is the boundary of the "< pivot" region: everything in nums[lo..i) is
  // known to be smaller than the pivot. It starts empty (i == lo).
  let i = lo;
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, nums.length - 1).
function quickSort(nums: number[], lo: number, hi: number): void {
  // Divide and conquer. Base case: a range of 0 or 1 element is already
  // sorted, so there's nothing to do.
  if (lo >= hi) {
    return;
  }

  // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
  // returning the index p the pivot lands on. Afterwards everything left of p
  // is < pivot, everything right is >= pivot, and the pivot sits in its final
  // sorted position.
  const p = partition(nums, lo, hi);

  // The pivot at p is already correct, so recurse on the two sides only —
  // never on p itself. That shrinking range is what guarantees termination.
  quickSort(nums, lo, p - 1);
  quickSort(nums, p + 1, hi);
}

// Lomuto partition scheme — the simplest way to partition. It takes the LAST
// element as the pivot and makes a single left-to-right pass, keeping a boundary
// between "seen values that are < pivot" and everything else. (The alternative,
// Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
// right. Lomuto is the one to memorize first.)
function partition(nums: number[], lo: number, hi: number): number {
  // Pivot = the last element. Any element works; picking the last one is
  // simplest, but on already-sorted input it causes the O(n^2) worst case —
  // production code often picks a random or median-of-three pivot instead.
  const pivot = nums[hi];

  // i is the boundary of the "< pivot" region: everything in nums[lo..i) is
  // known to be smaller than the pivot. It starts empty (i == lo).
  let i = lo;

  // Scan every element before the pivot with j.
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, nums.length - 1).
function quickSort(nums: number[], lo: number, hi: number): void {
  // Divide and conquer. Base case: a range of 0 or 1 element is already
  // sorted, so there's nothing to do.
  if (lo >= hi) {
    return;
  }

  // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
  // returning the index p the pivot lands on. Afterwards everything left of p
  // is < pivot, everything right is >= pivot, and the pivot sits in its final
  // sorted position.
  const p = partition(nums, lo, hi);

  // The pivot at p is already correct, so recurse on the two sides only —
  // never on p itself. That shrinking range is what guarantees termination.
  quickSort(nums, lo, p - 1);
  quickSort(nums, p + 1, hi);
}

// Lomuto partition scheme — the simplest way to partition. It takes the LAST
// element as the pivot and makes a single left-to-right pass, keeping a boundary
// between "seen values that are < pivot" and everything else. (The alternative,
// Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
// right. Lomuto is the one to memorize first.)
function partition(nums: number[], lo: number, hi: number): number {
  // Pivot = the last element. Any element works; picking the last one is
  // simplest, but on already-sorted input it causes the O(n^2) worst case —
  // production code often picks a random or median-of-three pivot instead.
  const pivot = nums[hi];

  // i is the boundary of the "< pivot" region: everything in nums[lo..i) is
  // known to be smaller than the pivot. It starts empty (i == lo).
  let i = lo;

  // Scan every element before the pivot with j.
  for (let j = lo; j < hi; j++) {
  }
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, nums.length - 1).
function quickSort(nums: number[], lo: number, hi: number): void {
  // Divide and conquer. Base case: a range of 0 or 1 element is already
  // sorted, so there's nothing to do.
  if (lo >= hi) {
    return;
  }

  // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
  // returning the index p the pivot lands on. Afterwards everything left of p
  // is < pivot, everything right is >= pivot, and the pivot sits in its final
  // sorted position.
  const p = partition(nums, lo, hi);

  // The pivot at p is already correct, so recurse on the two sides only —
  // never on p itself. That shrinking range is what guarantees termination.
  quickSort(nums, lo, p - 1);
  quickSort(nums, p + 1, hi);
}

// Lomuto partition scheme — the simplest way to partition. It takes the LAST
// element as the pivot and makes a single left-to-right pass, keeping a boundary
// between "seen values that are < pivot" and everything else. (The alternative,
// Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
// right. Lomuto is the one to memorize first.)
function partition(nums: number[], lo: number, hi: number): number {
  // Pivot = the last element. Any element works; picking the last one is
  // simplest, but on already-sorted input it causes the O(n^2) worst case —
  // production code often picks a random or median-of-three pivot instead.
  const pivot = nums[hi];

  // i is the boundary of the "< pivot" region: everything in nums[lo..i) is
  // known to be smaller than the pivot. It starts empty (i == lo).
  let i = lo;

  // Scan every element before the pivot with j.
  for (let j = lo; j < hi; j++) {
    // Does nums[j] belong in the "< pivot" region? If so, swap it to the
    // boundary (position i), which places it just past the known-smaller run.

      // The region grew by one, so advance the boundary.
  }
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, nums.length - 1).
function quickSort(nums: number[], lo: number, hi: number): void {
  // Divide and conquer. Base case: a range of 0 or 1 element is already
  // sorted, so there's nothing to do.
  if (lo >= hi) {
    return;
  }

  // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
  // returning the index p the pivot lands on. Afterwards everything left of p
  // is < pivot, everything right is >= pivot, and the pivot sits in its final
  // sorted position.
  const p = partition(nums, lo, hi);

  // The pivot at p is already correct, so recurse on the two sides only —
  // never on p itself. That shrinking range is what guarantees termination.
  quickSort(nums, lo, p - 1);
  quickSort(nums, p + 1, hi);
}

// Lomuto partition scheme — the simplest way to partition. It takes the LAST
// element as the pivot and makes a single left-to-right pass, keeping a boundary
// between "seen values that are < pivot" and everything else. (The alternative,
// Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
// right. Lomuto is the one to memorize first.)
function partition(nums: number[], lo: number, hi: number): number {
  // Pivot = the last element. Any element works; picking the last one is
  // simplest, but on already-sorted input it causes the O(n^2) worst case —
  // production code often picks a random or median-of-three pivot instead.
  const pivot = nums[hi];

  // i is the boundary of the "< pivot" region: everything in nums[lo..i) is
  // known to be smaller than the pivot. It starts empty (i == lo).
  let i = lo;

  // Scan every element before the pivot with j.
  for (let j = lo; j < hi; j++) {
    // Does nums[j] belong in the "< pivot" region? If so, swap it to the
    // boundary (position i), which places it just past the known-smaller run.
    if (nums[j] < pivot) {
      [nums[i], nums[j]] = [nums[j], nums[i]];

      // The region grew by one, so advance the boundary.
      i++;
    }
  }
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, nums.length - 1).
function quickSort(nums: number[], lo: number, hi: number): void {
  // Divide and conquer. Base case: a range of 0 or 1 element is already
  // sorted, so there's nothing to do.
  if (lo >= hi) {
    return;
  }

  // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
  // returning the index p the pivot lands on. Afterwards everything left of p
  // is < pivot, everything right is >= pivot, and the pivot sits in its final
  // sorted position.
  const p = partition(nums, lo, hi);

  // The pivot at p is already correct, so recurse on the two sides only —
  // never on p itself. That shrinking range is what guarantees termination.
  quickSort(nums, lo, p - 1);
  quickSort(nums, p + 1, hi);
}

// Lomuto partition scheme — the simplest way to partition. It takes the LAST
// element as the pivot and makes a single left-to-right pass, keeping a boundary
// between "seen values that are < pivot" and everything else. (The alternative,
// Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
// right. Lomuto is the one to memorize first.)
function partition(nums: number[], lo: number, hi: number): number {
  // Pivot = the last element. Any element works; picking the last one is
  // simplest, but on already-sorted input it causes the O(n^2) worst case —
  // production code often picks a random or median-of-three pivot instead.
  const pivot = nums[hi];

  // i is the boundary of the "< pivot" region: everything in nums[lo..i) is
  // known to be smaller than the pivot. It starts empty (i == lo).
  let i = lo;

  // Scan every element before the pivot with j.
  for (let j = lo; j < hi; j++) {
    // Does nums[j] belong in the "< pivot" region? If so, swap it to the
    // boundary (position i), which places it just past the known-smaller run.
    if (nums[j] < pivot) {
      [nums[i], nums[j]] = [nums[j], nums[i]];

      // The region grew by one, so advance the boundary.
      i++;
    }
  }

  // The scan is done: nums[lo..i) < pivot and nums[i..hi) >= pivot, so index i
  // is exactly where the pivot belongs. Swap it in from the end.
}

// Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, nums.length - 1).
function quickSort(nums: number[], lo: number, hi: number): void {
  // Divide and conquer. Base case: a range of 0 or 1 element is already
  // sorted, so there's nothing to do.
  if (lo >= hi) {
    return;
  }

  // Partition picks a "pivot" value and rearranges nums[lo..hi] around it,
  // returning the index p the pivot lands on. Afterwards everything left of p
  // is < pivot, everything right is >= pivot, and the pivot sits in its final
  // sorted position.
  const p = partition(nums, lo, hi);

  // The pivot at p is already correct, so recurse on the two sides only —
  // never on p itself. That shrinking range is what guarantees termination.
  quickSort(nums, lo, p - 1);
  quickSort(nums, p + 1, hi);
}

// Lomuto partition scheme — the simplest way to partition. It takes the LAST
// element as the pivot and makes a single left-to-right pass, keeping a boundary
// between "seen values that are < pivot" and everything else. (The alternative,
// Hoare's scheme, walks two pointers inward: fewer swaps, but fiddlier to get
// right. Lomuto is the one to memorize first.)
function partition(nums: number[], lo: number, hi: number): number {
  // Pivot = the last element. Any element works; picking the last one is
  // simplest, but on already-sorted input it causes the O(n^2) worst case —
  // production code often picks a random or median-of-three pivot instead.
  const pivot = nums[hi];

  // i is the boundary of the "< pivot" region: everything in nums[lo..i) is
  // known to be smaller than the pivot. It starts empty (i == lo).
  let i = lo;

  // Scan every element before the pivot with j.
  for (let j = lo; j < hi; j++) {
    // Does nums[j] belong in the "< pivot" region? If so, swap it to the
    // boundary (position i), which places it just past the known-smaller run.
    if (nums[j] < pivot) {
      [nums[i], nums[j]] = [nums[j], nums[i]];

      // The region grew by one, so advance the boundary.
      i++;
    }
  }

  // The scan is done: nums[lo..i) < pivot and nums[i..hi) >= pivot, so index i
  // is exactly where the pivot belongs. Swap it in from the end.
  [nums[i], nums[hi]] = [nums[hi], nums[i]];
  return i;
}

class Solution {
    // Sorts nums[lo..hi] in place. Call it as quickSort(nums, 0, nums.length - 1).
    static void quickSort(int[] nums, int lo, int hi) {
        
    }
}