Detailed explanation of the implementation method and application of sort package in go language

type Interface interface {
 // Return the length of data to be sorted Len() int
 //Compare the data sizes corresponding to i and j, and you can control ascending and descending order by yourselfLess(i, j int) bool
 // Exchange the data corresponding to the subscript i and j Swap(i, j int)
}

type Person struct {
 Name string
 Age int
}

type ByAge []Person
//Implement three methods in the sort interface, and you can use the sort methodfunc (a ByAge) Len() int   { return len(a) }
func (a ByAge) Swap(i, j int)  { a[i], a[j] = a[j], a[i] }
func (a ByAge) Less(i, j int) bool { return a[i].Age < a[j].Age }

func Example() {
 people := []Person{
  {"Bob", 31},
  {"John", 42},
  {"Michael", 17},
  {"Jenny", 26},
 }

 (people)
 (ByAge(people)) //The Sort() method in the sort package is called here. Let's take a look at this method (people)

 // Output:
 // [Bob: 31 John: 42 Michael: 17 Jenny: 26]
 // [Michael: 17 Jenny: 26 Bob: 31 John: 42]
}

//The sort package only provides this publicly used sorting method.func Sort(data Interface) {
 // Switch to heapsort if depth of 2*ceil(lg(n+1)) is reached.
 //If the element depth reaches 2*ceil(lg(n+1)), select heap sort n := ()
 maxDepth := 0
 for i := n; i > 0; i >>= 1 {
  maxDepth++
 }
 maxDepth *= 2
 quickSort(data, 0, n, maxDepth)
}

//Quick sort//It will automatically choose whether to sort with heap, insert or quick sort. Quick sort isfunc quickSort(data Interface, a, b, maxDepth int) {
 // If there are fewer than twelve slice elements, use the Hill insertion method for b-a > 12 { // Use ShellSort for slices <= 12 elements
  if maxDepth == 0 {
   heapSort(data, a, b) //Heap sorting method, a=0, b=n   return
  }
  maxDepth--
  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 // ., quickSort(data, mhi, b)
  } else {
   quickSort(data, mhi, b, maxDepth)
   b = mlo // ., quickSort(data, a, mlo)
  }
 }
 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 (i, i-6) {
    (i, i-6)
   }
  }
  insertionSort(data, a, b)
 }
}

//Heap sortfunc heapSort(data Interface, a, b int) {
 first := a
 lo := 0
 hi := b - a

 // Build heap with greatest element at top.
 //Build a heap structure, the top of the largest element is to build a large root heap for i := (hi - 1) / 2; i >= 0; i-- {
  siftDown(data, i, hi, first)
 }

 // Pop elements, largest first, into end of data.
 //Insert first into the end of data for i := hi - 1; i >= 0; i-- {
  (first, first+i) //Data exchange  siftDown(data, lo, i, first) //Heap re-filter }
}

// 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) {
 //hi is the length of the array //There is a way here to save the following elements, but for the purpose of being more abstract, this one is saved, and instead exchange them in swap. root := lo //Subscript of root element for {
  child := 2*root + 1 //Subscript of the left leaf node  //Introduction to control for loops, this writing method is simpler. You can view the articles I wrote about heap sorting  if child >= hi { 
   break
  }
  //Prevent array subscripts from crossing the boundary, and determine which big one is left and right children  if child+1 < hi && (first+child, first+child+1) { 
   child++
  }
  //Judge the relationship between the largest child and the root element  if !(first+root, first+child) {
   return
  }
  //If all the above is satisfied, data exchange will be performed  (first+root, first+child)
  root = child
 }
}