Five basic sorting algorithms are implemented in the sort package: insert sort, Hill sort, heap sort, quick sort and merge sort. Like other languages, these five algorithms are not public and are only used inside the sort package.
sort.Interface interface
The types that implement sort.interface (generally a collection) can be sorted using the functions in the sort package. The definition of sort.interface interface is as follows:
type Interface interface {
// The Len method returns the number of elements in the collection
Len() int
// The Less method reports whether the element of index i is smaller than the element of index j
Less(i, j int) bool
// The Swap method swaps the two elements of indexes i and j
Swap(i, j int)
}
Custom type sorting
Sort/Stable function
// Sorting data does not guarantee stability, that is, the relative order of equal elements may change // Sort calls data.Len once to determine the length, and O(n*log(n)) calls data.Less and data.Swap func Sort(data Interface) // Sort data to ensure the stability of sorting, that is, the relative order of equal elements remains unchanged // Sort calls data.Len once, O(n*log(n)) times data.Less and O(n*log(n)*log(n)) times data.Swap func Stable(data Interface) // Wrap a sort.Interface interface interface and return a new sort.Interface interface, which can be sorted to generate a decreasing sequence func Reverse(data Interface) Interface // Determine whether the data has been sorted func IsSorted(data Interface) bool
The example code is as follows:
type Student struct {
Name string
Age int
}
type StudentSlice []Student
// Implement the sort.Interface interface
func (ss StudentSlice) Len() int {
return len(ss)
}
func (ss StudentSlice) Less(i, j int) bool {
return ss[i].Age < ss[j].Age
}
func (ss StudentSlice) Swap(i, j int) {
ss[i], ss[j] = ss[j], ss[i]
}
func main() {
ss := StudentSlice{
{"Alice", 18},
{"Bob", 20},
{"Allen", 16},
{"Michelle", 18},
{"James", 24},
}
// In ascending order of age
sort.Sort(ss)
fmt.Println(ss) // [{Allen 16} {Alice 18} {Michelle 18} {Bob 20} {James 24}]
fmt.Println(sort.IsSorted(ss)) // true
// In descending order of age
sort.Sort(sort.Reverse(ss))
fmt.Println(ss) // [{James 24} {Bob 20} {Alice 18} {Michelle 18} {Allen 16}]
fmt.Println(sort.IsSorted(ss)) // false
}
Slice/SliceStable function
In the sorting of the previous Sort/Stable functions, slices of custom types need to implement the sort.Interface interface, which is not very concise in code. Go provides Slice/SliceStable functions. You only need to pass in a slice to be sorted and a callback function to sort. Note that except for the following three functions, the input parameter object x interface {} of all other functions in the sort package needs to implement the sort.Interface interface. The reason will be analyzed later.
// Using the rules defined by the less function to sort slice X does not guarantee the stability of sorting. If x is not a slice, it will report panic
func Slice(x interface{}, less func(i, j int) bool)
// Use the rules defined by the less function to sort slice x to ensure the stability of sorting. If x is not a slice, it will report panic
func SliceStable(x interface{}, less func(i, j int) bool)
// Judge whether the slice x is ordered according to the rules defined by the less function. If x is not a slice, panic will be reported
func SliceIsSorted(x interface{}, less func(i, j int) bool)
The example code is as follows:
type Student struct {
Name string
Age int
}
func main() {
ss := []Student{
{"Alice", 18},
{"Bob", 20},
{"Allen", 16},
{"Michelle", 18},
{"James", 24},
}
less := func(i, j int) bool {
return ss[i].Age < ss[j].Age
}
// In ascending order of age
sort.Slice(ss, less)
fmt.Println(ss) // [{Allen 16} {Alice 18} {Michelle 18} {Bob 20} {James 24}]
fmt.Println(sort.SliceIsSorted(ss, less)) // true
}
Basic data type sorting
For slices of int, float64 and string types, Go language encapsulates them, and you can directly call the sort package function for sorting.
int type sort
// Under the sort package, the Go language defines the IntSlice type and implements the sort.Interface interface for [] int sorting
type IntSlice []int
// Implement Interface
func (x IntSlice) Len() int { return len(x) }
func (x IntSlice) Less(i, j int) bool { return x[i] < x[j] }
func (x IntSlice) Swap(i, j int) { x[i], x[j] = x[j], x[i] }
// Equivalent call sort.Sort(x)
func (x IntSlice) Sort() { Sort(x) }
// Equivalent call sort.SearchInts(x, p)
func (x IntSlice) Search(p int) int { return SearchInts(x, p) }
// Sort x in ascending order func Ints(x []int) // Determine whether x is in ascending order func IntsAreSorted(x []int) // Search for x in a in ascending order and return the index of x // If it cannot be found, the return value is the position where x should be inserted into a (to ensure the increasing order of a), and the return value can be len(a) func SearchInts(a []int, x int) int
The example code is as follows:
func main() {
// Ascending mode 1:
intList1 := []int{2, 0, 1, 8, 0, 9, 2, 4, 1, 2}
sort.Ints(intList1)
fmt.Println(intList1) // [0 0 1 1 2 2 2 4 8 9]
// Ascending mode 2:
intList2 := []int{2, 0, 1, 8, 0, 9, 2, 4, 1, 2}
sort.Sort(sort.IntSlice(intList2))
fmt.Println(intList2) // [0 0 1 1 2 2 2 4 8 9]
// Ascending method 3:
intList3 := []int{2, 0, 1, 8, 0, 9, 2, 4, 1, 2}
(sort.IntSlice(intList3)).Sort()
fmt.Println(intList3) // [0 0 1 1 2 2 2 4 8 9]
// Descending order:
intList4 := []int{2, 0, 1, 8, 0, 9, 2, 4, 1, 2}
sort.Sort(sort.Reverse(sort.IntSlice(intList4)))
fmt.Println(intList4) // [9 8 4 2 2 2 1 1 0 0]
intList5 := []int{0, 0, 1, 1, 2, 2, 2, 4, 8, 9}
// Search method 1:
fmt.Println(sort.SearchInts(intList5, 2)) // 4
// Search method 2:
fmt.Println(sort.IntSlice(intList5).Search(2)) // 4
}
float64 type sorting
// Under the sort package, the Go language defines the Float64Slice type and implements the sort.Interface interface for [] float64 sorting
type Float64Slice []float64
// Implement Interface
func (x Float64Slice) Len() int { return len(x) }
func (x Float64Slice) Less(i, j int) bool { return x[i] < x[j] || (isNaN(x[i]) && !isNaN(x[j])) }
func (x Float64Slice) Swap(i, j int) { x[i], x[j] = x[j], x[i] }
// Equivalent call sort.Sort(x)
func (x Float64Slice) Sort() { Sort(x) }
// Equivalent call sort.SearchFloat64s(x, p)
func (x Float64Slice) Search(p float64) int { return SearchFloat64s(x, p) }
// Sort x in ascending order func Float64s(x []float64) // Determine whether x is in ascending order func Float64sAreSorted(x []float64) // Search for x in a in ascending order and return the index of x // If it cannot be found, the return value is the position where x should be inserted into a (to ensure the increasing order of a), and the return value can be len(a) func SearchFloat64s(a []float64, x float64) int
The example code is as follows:
func main() {
// Ascending mode 1:
floatList1 := []float64{4.2, 5.9, 12.3, 10.0, 50.4, 99.9, 31.4, 27.81828, 3.14}
sort.Float64s(floatList1)
fmt.Println(floatList1) // [3.14 4.2 5.9 10 12.3 27.81828 31.4 50.4 99.9]
// Ascending mode 2:
floatList2 := []float64{4.2, 5.9, 12.3, 10.0, 50.4, 99.9, 31.4, 27.81828, 3.14}
sort.Sort(sort.Float64Slice(floatList2))
fmt.Println(floatList2) // [3.14 4.2 5.9 10 12.3 27.81828 31.4 50.4 99.9]
// Ascending method 3:
floatList3 := []float64{4.2, 5.9, 12.3, 10.0, 50.4, 99.9, 31.4, 27.81828, 3.14}
(sort.Float64Slice(floatList3)).Sort()
fmt.Println(floatList3) // [3.14 4.2 5.9 10 12.3 27.81828 31.4 50.4 99.9]
// Descending order:
floatList4 := []float64{4.2, 5.9, 12.3, 10.0, 50.4, 99.9, 31.4, 27.81828, 3.14}
sort.Sort(sort.Reverse(sort.Float64Slice(floatList4)))
fmt.Println(floatList4) // [99.9 50.4 31.4 27.81828 12.3 10 5.9 4.2 3.14]
floatList5 := []float64{3.14, 4.2, 5.9, 10, 12.3, 27.81828, 31.4, 50.4, 99.9}
// Search method 1:
fmt.Println(sort.SearchFloat64s(floatList5, 12.3)) // 4
// Search method 2:
fmt.Println(sort.Float64Slice(floatList5).Search(12.3)) // 4
}
string type sorting
// Under the sort package, the Go language defines the StringSlice type and implements the sort.Interface interface for [] string sorting
type StringSlice []string
// Implement Interface
func (x StringSlice) Len() int { return len(x) }
func (x StringSlice) Less(i, j int) bool { return x[i] < x[j] }
func (x StringSlice) Swap(i, j int) { x[i], x[j] = x[j], x[i] }
// Equivalent call sort.Sort(x)
func (x StringSlice) Sort() { Sort(x) }
// Equivalent call sort.SearchStrings(x, p)
func (x StringSlice) Search(p string) int { return SearchStrings(x, p) }
// Sort x in ascending order func Strings(x []string) // Determine whether x is in ascending order func StringsAreSorted(x []string) // Search for x in a in ascending order and return the index of x // If it cannot be found, the return value is the position where x should be inserted into a (to ensure the increasing order of a), and the return value can be len(a) func SearchStrings(a []string, x string) int
The example code is as follows:
func main() {
// Ascending mode 1:
stringList1 := []string{"o", "l", "d", "b", "o", "y", "g", "o", "l", "a", "n", "g"}
sort.Strings(stringList1)
fmt.Printf("%q\n", stringList1) // ["a" "b" "d" "g" "g" "l" "l" "n" "o" "o" "o" "y"]
// Ascending mode 2:
stringList2 := []string{"o", "l", "d", "b", "o", "y", "g", "o", "l", "a", "n", "g"}
sort.Sort(sort.StringSlice(stringList2))
fmt.Printf("%q\n", stringList2) // ["a" "b" "d" "g" "g" "l" "l" "n" "o" "o" "o" "y"]
// Ascending mode 3:
stringList3 := []string{"o", "l", "d", "b", "o", "y", "g", "o", "l", "a", "n", "g"}
(sort.StringSlice(stringList3)).Sort()
fmt.Printf("%q\n", stringList3) // ["a" "b" "d" "g" "g" "l" "l" "n" "o" "o" "o" "y"]
// Descending order:
stringList4 := []string{"o", "l", "d", "b", "o", "y", "g", "o", "l", "a", "n", "g"}
sort.Sort(sort.Reverse(sort.StringSlice(stringList4)))
fmt.Printf("%q\n", stringList4) // ["y" "o" "o" "o" "n" "l" "l" "g" "g" "d" "b" "a"]
stringList5 := []string{"a", "b", "d", "g", "g", "l", "l", "n", "o", "o", "o", "y"}
// Search method 1:
fmt.Println(sort.SearchStrings(stringList5, "l")) // 5
// Search method 2:
fmt.Println((sort.StringSlice(stringList5)).Search("l")) // 5
}
Bottom implementation analysis
sort.Sort function
// Sort function is an unstable sort method, which uses one of three sorting methods: Hill quick sort, quick sort or heap sort
func Sort(data Interface) {
n := data.Len()
// maxDepth(n) returns 2*ceil(lg(n+1)). If the element depth reaches 2*ceil(lg(n+1)), heap sorting is selected
quickSort(data, 0, n, maxDepth(n))
}
// quickSort will automatically select one of three sorting methods: quick, quick sort or heap sort according to the and element depth
func quickSort(data Interface, a, b, maxDepth int) {
for b-a > 12 {
if maxDepth == 0 { // Use ShellSort for slices <= 12 elements
// Use heap sort
heapSort(data, a, b)
return
}
maxDepth--
// Use three-dimensional segmentation quick sorting to partition the quick row through doPivot
mlo, mhi := doPivot(data, a, b)
// Avoiding recursion on the larger subproblem guarantees
// a stack depth of at most lg(b-a).
if mlo-a < b-mhi {
quickSort(data, a, mlo, maxDepth)
a = mhi // i.e., quickSort(data, mhi, b)
} else {
quickSort(data, mhi, b, maxDepth)
b = mlo // i.e., quickSort(data, a, mlo)
}
}
// Slice elements less than or equal to 12, using Hill sort (Hill sort is an efficient version of insert sort), with an interval of d=6
if b-a > 1 {
// Do ShellSort pass with gap 6
// It could be written in this simplified form cause b-a <= 12
for i := a + 6; i < b; i++ {
if data.Less(i, i-6) {
data.Swap(i, i-6)
}
}
insertionSort(data, a, b)
}
}
// Heap sort
func heapSort(data Interface, a, b int) {
first := a
lo := 0
hi := b - a
// Build heap with greatest element at top.
for i := (hi - 1) / 2; i >= 0; i-- {
siftDown(data, i, hi, first)
}
// Pop elements, largest first, into end of data.
for i := hi - 1; i >= 0; i-- {
data.Swap(first, first+i)
siftDown(data, lo, i, first)
}
}
// siftDown implements the heap property on data[lo:hi].
// first is an offset into the array where the root of the heap lies.
func siftDown(data Interface, lo, hi, first int) {
root := lo
for {
child := 2*root + 1
if child >= hi {
break
}
if child+1 < hi && data.Less(first+child, first+child+1) {
child++
}
if !data.Less(first+root, first+child) {
return
}
data.Swap(first+root, first+child)
root = child
}
}
// Insert sort
// insertionSort sorts data[a:b] using insertion sort.
func insertionSort(data Interface, a, b int) {
for i := a + 1; i < b; i++ {
for j := i; j > a && data.Less(j, j-1); j-- {
data.Swap(j, j-1)
}
}
}
sort.Stable function
// Stable is a stable sort, using merge sort
func Stable(data Interface) {
stable(data, data.Len())
}
// The merge sort algorithm used here is an original address sort algorithm:
// First, it sorts slices by inserting each blockSize=20 elements into a slice
// Loop merge two adjacent blocks, and double the blockSize each time until blockSize > n
func stable(data Interface, n int) {
// The initial blockSize is set to 20
blockSize := 20 // must be > 0
a, b := 0, blockSize
// Insert sort each block (and one block with less than blockSize remaining)
for b <= n {
insertionSort(data, a, b)
a = b
b += blockSize
}
insertionSort(data, a, n)
for blockSize < n {
a, b = 0, 2*blockSize
for b <= n {
// Merge every two blocksizes
symMerge(data, a, a+blockSize, b)
a = b
b += 2 * blockSize
}
// The remaining one or more blocksizes are merged
if m := a + blockSize; m < n {
symMerge(data, a, m, n)
}
blockSize *= 2
}
}
func symMerge(data Interface, a, m, b int) {
// Avoid unnecessary recursions of symMerge
// by direct insertion of data[a] into data[m:b]
// if data[a:m] only contains one element.
if m-a == 1 {
// Use binary search to find the lowest index i
// such that data[i] >= data[a] for m <= i < b.
// Exit the search loop with i == b in case no such index exists.
i := m
j := b
for i < j {
h := int(uint(i+j) >> 1)
if data.Less(h, a) {
i = h + 1
} else {
j = h
}
}
// Swap values until data[a] reaches the position before i.
for k := a; k < i-1; k++ {
data.Swap(k, k+1)
}
return
}
// Avoid unnecessary recursions of symMerge
// by direct insertion of data[m] into data[a:m]
// if data[m:b] only contains one element.
if b-m == 1 {
// Use binary search to find the lowest index i
// such that data[i] > data[m] for a <= i < m.
// Exit the search loop with i == m in case no such index exists.
i := a
j := m
for i < j {
h := int(uint(i+j) >> 1)
if !data.Less(m, h) {
i = h + 1
} else {
j = h
}
}
// Swap values until data[m] reaches the position i.
for k := m; k > i; k-- {
data.Swap(k, k-1)
}
return
}
mid := int(uint(a+b) >> 1)
n := mid + m
var start, r int
if m > mid {
start = n - b
r = mid
} else {
start = a
r = m
}
p := n - 1
for start < r {
c := int(uint(start+r) >> 1)
if !data.Less(p-c, c) {
start = c + 1
} else {
r = c
}
}
end := n - start
if start < m && m < end {
rotate(data, start, m, end)
}
if a < start && start < mid {
symMerge(data, a, start, mid)
}
if mid < end && end < b {
symMerge(data, mid, end, b)
}
}
sort.Slice function
// Slice function is an unstable sort method, which uses one of three sorting methods: Hill quick, quick sort or heap sort
// Slice sorts the slice x given the provided less function.
// It panics if x is not a slice.
//
// The sort is not guaranteed to be stable: equal elements
// may be reversed from their original order.
// For a stable sort, use SliceStable.
//
// The less function must satisfy the same requirements as
// the Interface type's Less method.
func Slice(x interface{}, less func(i, j int) bool) {
rv := reflectValueOf(x)
swap := reflectSwapper(x)
length := rv.Len()
// maxDepth(n) returns 2*ceil(lg(n+1)). If the element depth reaches 2*ceil(lg(n+1)), heap sorting is selected
quickSort_func(lessSwap{less, swap}, 0, length, maxDepth(length))
}
// lessSwap is a pair of Less and Swap function for use with the
// auto-generated func-optimized variant of sort.go in
// zfuncversion.go.
type lessSwap struct {
Less func(i, j int) bool
Swap func(i, j int)
}
// quickSort_func will automatically select one of three sorting methods: quick sort, quick sort or heap sort according to the and element depth
// Auto-generated variant of sort.go:quickSort
func quickSort_func(data lessSwap, a, b, maxDepth int) {
for b-a > 12 {
if maxDepth == 0 {
// Use heap sort
heapSort_func(data, a, b)
return
}
maxDepth--
// Use three-way segmentation to quickly sort through doPivot_func partition for fast scheduling
mlo, mhi := doPivot_func(data, a, b)
if mlo-a < b-mhi {
quickSort_func(data, a, mlo, maxDepth)
a = mhi
} else {
quickSort_func(data, mhi, b, maxDepth)
b = mlo
}
}
// Slice elements less than or equal to 12, using Hill sort (Hill sort is an efficient version of insert sort), with an interval of d=6
if b-a > 1 {
for i := a + 6; i < b; i++ {
if data.Less(i, i-6) {
data.Swap(i, i-6)
}
}
insertionSort_func(data, a, b)
}
}
As you can see from the above, the sort function quicksort called by sort. Slice_ The input parameter type of func is data lesswap instead of data Interface. The insertion sort, heap sort and quick sort functions called are also different from sort.Sort. The implementation principles of sort.Slice and sort.Sort are the same. The difference is that sort.Sort obtains Len()/Swap()/Less() by passing in the object implementing the sort.Interface interface, while sort.Slice obtains Len() and Swap() / Less() by reflection, and Less() by passing parameters. Therefore, the object passed in by sort. Slice does not need to implement the sort. Interface interface interface.
sort.SliceStable function
// SliceStable is a stable sort that uses merge sort
// SliceStable sorts the slice x using the provided less
// function, keeping equal elements in their original order.
// It panics if x is not a slice.
//
// The less function must satisfy the same requirements as
// the Interface type's Less method.
func SliceStable(x interface{}, less func(i, j int) bool) {
rv := reflectValueOf(x)
swap := reflectSwapper(x)
stable_func(lessSwap{less, swap}, rv.Len())
}
// lessSwap is a pair of Less and Swap function for use with the
// auto-generated func-optimized variant of sort.go in
// zfuncversion.go.
type lessSwap struct {
Less func(i, j int) bool
Swap func(i, j int)
}
// The merge sort algorithm used here is an original address sort algorithm:
// First, it sorts slices by inserting each blockSize=20 elements into a slice
// Loop merge two adjacent blocks, and double the blockSize each time until blockSize > n
// Auto-generated variant of sort.go:stable
func stable_func(data lessSwap, n int) {
blockSize := 20 // The initial blockSize is set to 20
a, b := 0, blockSize
// Insert sort each block (and one block with less than blockSize remaining)
for b <= n {
insertionSort_func(data, a, b)
a = b
b += blockSize
}
insertionSort_func(data, a, n)
for blockSize < n {
a, b = 0, 2*blockSize
for b <= n {
// Merge every two blocksizes
symMerge_func(data, a, a+blockSize, b)
a = b
b += 2 * blockSize
}
// The remaining one or more blocksizes are merged
if m := a + blockSize; m < n {
symMerge_func(data, a, m, n)
}
blockSize *= 2
}
}
Like sort.Slice, sort.SliceStable calls the sort function stable_ The input parameter type of func is data lesswap, not data Interface. Len() and Swap() are obtained by reflection, and Less() is obtained by passing parameters.