Go标准库中的sort是如何实现的？

// pdqsort sorts data[a:b].
// The algorithm based on pattern-defeating quicksort(pdqsort), 
// but without the optimizations from BlockQuicksort.
// pdqsort paper: https://arxiv.org/pdf/2106.05123.pdf
// C++ implementation: https://github.com/orlp/pdqsort
// Rust implementation: https://docs.rs/pdqsort/latest/pdqsort/
// limit is the number of allowed bad (very unbalanced) pivots 
// before falling back to heapsort.
func pdqsort(data Interface, a, b, limit int) {
  const maxInsertion = 12
  
  var (
    wasBalanced    = true // whether the last partitioning was reasonably balanced
    wasPartitioned = true // whether the slice was already partitioned
  )
  
  for {
    length := b - a
    
    if length <= maxInsertion {
            insertionSort(data, a, b)
            return
    }
    
    // Fall back to heapsort if too many bad choices were made.
    if limit == 0 {
            heapSort(data, a, b)
            return
    }
    
    // If the last partitioning was imbalanced, we need to    breaking patterns.
    if !wasBalanced {
            breakPatterns(data, a, b)
            limit--
    }
    
    pivot, hint := choosePivot(data, a, b)
    if hint == decreasingHint {
            reverseRange(data, a, b)
            // The chosen pivot was pivot-a elements after the start of the array.
            // After reversing it is pivot-a elements before the end of the array.
            // The idea came from Rust's implementation.
            pivot = (b - 1) - (pivot - a)
            hint = increasingHint
    }
    
    // The slice is likely already sorted.
    if wasBalanced && wasPartitioned && hint == increasingHint {
            if partialInsertionSort(data, a, b) {
                    return
            }
    }
    
    // Probably the slice contains many duplicate elements,    
    // partition the slice into
    // elements equal to and elements greater than the pivot.
    if a > 0 && !data.Less(a-1, pivot) {
            mid := partitionEqual(data, a, b, pivot)
            a = mid
            continue
    }
    
    mid, alreadyPartitioned := partition(data, a, b, pivot)
    wasPartitioned = alreadyPartitioned
    
    leftLen, rightLen := mid-a, b-mid
    balanceThreshold := length / 8
    if leftLen < rightLen {
            wasBalanced = leftLen >= balanceThreshold
            pdqsort(data, a, mid, limit)
            a = mid + 1
    } else {
            wasBalanced = rightLen >= balanceThreshold
            pdqsort(data, mid+1, b, limit)
            b = mid
    }
  }
}

func Sort(data Interface) {
        n := data.Len()
        if n <= 1 {
                return
        }
        limit := bits.Len(uint(n))
        pdqsort(data, 0, n, limit)
}

balanceThreshold := length / 8
if leftLen < rightLen {
        wasBalanced = leftLen >= balanceThreshold
        ...
} else {
        wasBalanced = rightLen >= balanceThreshold
        ...
}

// breakPatterns scatters some elements around in an attempt to break some patterns
// that might cause imbalanced partitions in quicksort.
func breakPatterns(data Interface, a, b int) {
  length := b - a
  if length >= 8 {
    random := xorshift(length)
    modulus := nextPowerOfTwo(length)  
    for idx := a + (length/4)*2 - 1; idx <= a+(length/4)*2+1; id  ++ {
       other := int(uint(random.Next()) & (modulus - 1))
       if other >= length {
          other -= length
       }
       data.Swap(idx, a+other)
    }
}

func choosePivot(data Interface, a, b int) (pivot int, hint sortedHint) {
  const (
          shortestNinther = 50
          maxSwaps        = 4 * 3
  )  
  l := b - a  
  var (
          swaps int
          i     = a + l/4*1
          j     = a + l/4*2
          k     = a + l/4*3
  )  
  if l >= 8 {
    if l >= shortestNinther {
            // Tukey ninther method, the idea came from Rust's implementation.
            i = medianAdjacent(data, i, &swaps)
            j = medianAdjacent(data, j, &swaps)
            k = medianAdjacent(data, k, &swaps)
    }
    // Find the median among i, j, k and stores it into j.
    j = median(data, i, j, k, &swaps)
  }  
  switch swaps {
  case 0:
          return j, increasingHint
  case maxSwaps:
          return j, decreasingHint
  default:
          return j, unknownHint
  }
}

// partialInsertionSort partially sorts a slice, returns true if the slice is sorted at the end.
func partialInsertionSort(data Interface, a, b int) bool {
  const (
          maxSteps         = 5  // maximum number of adjacent out-of-order pairs that will get shifted
          shortestShifting = 50 // don't shift any elements on short arrays
  )
  i := a + 1
  for j := 0; j < maxSteps; j++ {
    for i < b && !data.Less(i, i-1) {
            i++
    }  
    if i == b {
            return true
    }  
    if b-a < shortestShifting {
            return false
    }  
    data.Swap(i, i-1)  
    // Shift the smaller one to the left.
    if i-a >= 2 {
            for j := i - 1; j >= 1; j-- {
                    if !data.Less(j, j-1) {
                            break
                    }
                    data.Swap(j, j-1)
            }
    }
    // Shift the greater one to the right.
    if b-i >= 2 {
            for j := i + 1; j < b; j++ {
                    if !data.Less(j, j-1) {
                            break
                    }
                    data.Swap(j, j-1)
            }
    }
  }
  return false
}