Heap sort

Heap sort. Time complexity O(nlognnlognnlogn). Space complexity O(1). Sort in place. Unstable sort.

The code is as follows (submitted in LeetCode). Topic link

func sortArray(nums []int) []int {
    l := len(nums)
    if l < 2 {
        return nums
    }
    end := l- 1
    // heap as a whole
    for i := (end- 1) /2; i >= 0; i-- {
        heapify(nums, i, end)
    }
    / / sorting
    for i := end; i > 0; i-- {
        nums[0], nums[i] = nums[i], nums[0]
        heapify(nums, 0, i- 1)}return nums
}

/ / heap
func heapify(a []int, b, e int) {
    var (
        p = b
        pv = a[p]
    )
    for {
        child := 2*p+1
        if child > e {
            break
        }
        if child+1 <= e && a[child+1] > a[child] {
            child++
        }
        if pv >= a[child] {
            break
        }
        a[p] = a[child]
        p = child
    }
    a[p] = pv
}
Copy the code