原理

1丶设置第一个元素为标记数
2、将小于标记数的放在标记数的左边，大于中间数的放在中间数的右边
3、左边所有元素执行1操作做，右边所有元素执行1操作

Go代码

package main

import (
    "fmt"
)

func main() {
    arr := []int{4, 3, 9, 6}
    sort(arr)
}
func sort(arr []int) {
    merge(arr, 0, len(arr)-1)

}

func merge(arr []int, start int, end int) {
    if start >= end {
        return

    }
    key := arr[start]
    li := start
    ri := end
    for li != ri {
        for li < ri && arr[ri] >= key {
            ri--

        }
        for li < ri && arr[li] <= key {
            li++

        }

        if li < ri {
            arr[li], arr[ri] = arr[ri], arr[li]

        }
    }

    arr[li], arr[start] = key, arr[li]
    merge(arr, start, li-1)
    merge(arr, li+1, end)
}