IntroSort Based on Binary segmentation

Submitted in niuke network through, corresponding topic

/ / the entry
func Sort(a []int) {
    l := len(a)
    if l < 2 {
        return
    }
    sort(a, 0, l- 1, getMaxDepth(l))
}

// Control the maximum depth of recursion
func getMaxDepth(n int) int {
    var depth int
    for i := n; i > 0; i >>= 1 {
        depth++
    }
    return 2*depth
}

// recursive call
func sort(a []int, low, high, depth int) {
    // high-low+1 > 12
    if high-low > 11 {
        if depth == 0 {
            // Use heap sort instead for maximum recursion depth
            heapSort(a, low, high)
        } else {
            depth--
            pivotIndex := partition(a, low, high)
            sort(a, low, pivotIndex- 1, depth)
            sort(a, pivotIndex+1, high, depth)
        }
    } else {
        // Use insertion sort between cells
        insertionSort(a, low, high)
    }
}

func heapSort(a []int, low, high int) {
    // The loop variable used when processing the heap is evaluated based on 0
    // The index for reading and writing elements of array A is calculated based on low
    // l := high-low+1
    // end := l-1
    end := high-low
    for i := (end- 1) /2; i >= 0; i-- {
        heapify(a, i, end, low)
    }
    for i := end; i > 0; i-- {
        a[low], a[low+i] = a[low+i], a[low] // a[low] = a[low+0]
        heapify(a, 0, i- 1, low)
    }
}

// Adjust downward
func heapify(a []int, b, e, low int) {
    // The loop variable used when processing the heap is calculated based on b
    // The index for reading and writing elements of array A is calculated based on low
    p := b
    pv := a[low+p]
    for {
        child := 2*p + 1
        if child > e {
            break
        }
        if child+1 <= e && a[low+child+1] > a[low+child] {
            child++
        }
        if pv >= a[low+child] {
            break
        }
        a[low+p] = a[low+child]
        p = child
    }
    a[low+p] = pv
}

func insertionSort(a []int, low, high int) {
    for i := low+1; i <= high; i++ {
        n := a[i]
        j := i- 1
        for j >= low && a[j] > n {
            a[j+1] = a[j]
            j--
        }
        a[j+1] = n
    }
}

// Range index range [low, high]
// Binary segmentation or "hole filling"
// Return value: the index position where pivot is placed after shard is complete
func partition(a []int, low, high int) int {
    selectPivot(a, low, high) // Place pivot on low index
    pivot := a[low] // The first pit
    for low < high {
        for low < high && a[high] >= pivot {
            high--
        }
        a[low] = a[high]
        for low < high && a[low] <= pivot {
            low++
        }
        a[high] = a[low]
    }
    a[low] = pivot
    return low
}

// Place the selected pivot element on the low index
func selectPivot(a []int, low, high int) {
    l := high-low+1
    mid := low + (high-low)>>1
    // l <= 40
    // if l > 40
    if l > 40 {
        seg := l/8
        medianOfThree(a, low, low+seg, low+2*seg)
        medianOfThree(a, mid, mid-seg, mid+seg)
        medianOfThree(a, high, high-seg, high2 -*seg)
    }
    medianOfThree(a, low, mid, high)
}

// select * from i1; // select * from i1; // Select * from i1
func medianOfThree(a []int, i1, i0, i2 int) {
    if a[i1] > a[i2] {
        a[i1], a[i2] = a[i2], a[i1]
    }
    if a[i0] > a[i2] {
        a[i0], a[i2] = a[i2], a[i0]
    }
    if a[i1] < a[i0] {
        a[i1], a[i0] = a[i0], a[i1]
    }
}
Copy the code