Quick Sort

func quickSort(nums []int, lo, hi int) {

}

func quickSort(nums []int, lo, hi int) {
    // Micropattern: sort [lo, hi] by splitting around a pivot.
}

func quickSort(nums []int, lo, hi int) {
    // Micropattern: sort [lo, hi] by splitting around a pivot.
    if lo >= hi {
        return // 0 or 1 elements are already sorted
    }
}

func quickSort(nums []int, lo, hi int) {
    // Micropattern: sort [lo, hi] by splitting around a pivot.
    if lo >= hi {
        return // 0 or 1 elements are already sorted
    }

    p := partition(nums, lo, hi)
}

func quickSort(nums []int, lo, hi int) {
    // Micropattern: sort [lo, hi] by splitting around a pivot.
    if lo >= hi {
        return // 0 or 1 elements are already sorted
    }

    p := partition(nums, lo, hi)

    // Everything left of p is smaller, everything right is larger.
}

func quickSort(nums []int, lo, hi int) {
    // Micropattern: sort [lo, hi] by splitting around a pivot.
    if lo >= hi {
        return // 0 or 1 elements are already sorted
    }

    p := partition(nums, lo, hi)

    // Everything left of p is smaller, everything right is larger.
    quickSort(nums, lo, p-1)
    quickSort(nums, p+1, hi)
}

func quickSort(nums []int, lo, hi int) {
    // Micropattern: sort [lo, hi] by splitting around a pivot.
    if lo >= hi {
        return // 0 or 1 elements are already sorted
    }

    p := partition(nums, lo, hi)

    // Everything left of p is smaller, everything right is larger.
    quickSort(nums, lo, p-1)
    quickSort(nums, p+1, hi)
}

// partition (Lomuto): place the pivot in its final spot, return its index.

func quickSort(nums []int, lo, hi int) {
    // Micropattern: sort [lo, hi] by splitting around a pivot.
    if lo >= hi {
        return // 0 or 1 elements are already sorted
    }

    p := partition(nums, lo, hi)

    // Everything left of p is smaller, everything right is larger.
    quickSort(nums, lo, p-1)
    quickSort(nums, p+1, hi)
}

// partition (Lomuto): place the pivot in its final spot, return its index.
func partition(nums []int, lo, hi int) int {
    pivot := nums[hi] // pick the last element as pivot
    i := lo           // boundary: nums[lo..i) are < pivot
}

func quickSort(nums []int, lo, hi int) {
    // Micropattern: sort [lo, hi] by splitting around a pivot.
    if lo >= hi {
        return // 0 or 1 elements are already sorted
    }

    p := partition(nums, lo, hi)

    // Everything left of p is smaller, everything right is larger.
    quickSort(nums, lo, p-1)
    quickSort(nums, p+1, hi)
}

// partition (Lomuto): place the pivot in its final spot, return its index.
func partition(nums []int, lo, hi int) int {
    pivot := nums[hi] // pick the last element as pivot
    i := lo           // boundary: nums[lo..i) are < pivot

    for j := lo; j < hi; j++ {
        if nums[j] < pivot {
            nums[i], nums[j] = nums[j], nums[i]
            i++
        }
    }
}

func quickSort(nums []int, lo, hi int) {
    // Micropattern: sort [lo, hi] by splitting around a pivot.
    if lo >= hi {
        return // 0 or 1 elements are already sorted
    }

    p := partition(nums, lo, hi)

    // Everything left of p is smaller, everything right is larger.
    quickSort(nums, lo, p-1)
    quickSort(nums, p+1, hi)
}

// partition (Lomuto): place the pivot in its final spot, return its index.
func partition(nums []int, lo, hi int) int {
    pivot := nums[hi] // pick the last element as pivot
    i := lo           // boundary: nums[lo..i) are < pivot

    for j := lo; j < hi; j++ {
        if nums[j] < pivot {
            nums[i], nums[j] = nums[j], nums[i]
            i++
        }
    }

    // Swap the pivot into position i.
}

func quickSort(nums []int, lo, hi int) {
    // Micropattern: sort [lo, hi] by splitting around a pivot.
    if lo >= hi {
        return // 0 or 1 elements are already sorted
    }

    p := partition(nums, lo, hi)

    // Everything left of p is smaller, everything right is larger.
    quickSort(nums, lo, p-1)
    quickSort(nums, p+1, hi)
}

// partition (Lomuto): place the pivot in its final spot, return its index.
func partition(nums []int, lo, hi int) int {
    pivot := nums[hi] // pick the last element as pivot
    i := lo           // boundary: nums[lo..i) are < pivot

    for j := lo; j < hi; j++ {
        if nums[j] < pivot {
            nums[i], nums[j] = nums[j], nums[i]
            i++
        }
    }

    // Swap the pivot into position i.
    nums[i], nums[hi] = nums[hi], nums[i]
    return i
}