Быстрые сортировки

func quickSort(a []int, lo, hi int) {
    if lo >= hi { return }
    p := partition(a, lo, hi)
    quickSort(a, lo, p-1)
    quickSort(a, p+1, hi)
}

func partition(a []int, lo, hi int) int {
    pivot := a[hi]
    i := lo
    for j := lo; j < hi; j++ {
        if a[j] <= pivot {
            a[i], a[j] = a[j], a[i]
            i++
        }
    }
    a[i], a[hi] = a[hi], a[i]
    return i
}

func mergeSort(a []int) []int {
    if len(a) <= 1 { return a }
    mid := len(a) / 2
    left := mergeSort(a[:mid])
    right := mergeSort(a[mid:])
    return merge(left, right)
}

func merge(l, r []int) []int {
    result := make([]int, 0, len(l)+len(r))
    i, j := 0, 0
    for i < len(l) && j < len(r) {
        if l[i] <= r[j] { result = append(result, l[i]); i++ } else { result = append(result, r[j]); j++ }
    }
    result = append(result, l[i:]...)
    return append(result, r[j:]...)
}

func heapSort(a []int) {
    n := len(a)
    for i := n/2 - 1; i >= 0; i-- { heapify(a, n, i) }
    for i := n - 1; i > 0; i-- {
        a[0], a[i] = a[i], a[0]
        heapify(a, i, 0)
    }
}

func heapify(a []int, n, i int) {
    largest, l, r := i, 2*i+1, 2*i+2
    if l < n && a[l] > a[largest] { largest = l }
    if r < n && a[r] > a[largest] { largest = r }
    if largest != i {
        a[i], a[largest] = a[largest], a[i]
        heapify(a, n, largest)
    }
}