Hands-On High Performance with Go

Heap sort

Go has a built-in heapSort in the standard library, as shown in the following code snippet. This code snippet helps us understand that heapSort is an O(n log n) sorting algorithm. This is better than our preceding insertion sort example, so for larger datasets, we are going to have more performant code when using our heap sort algorithm:

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)  }}

This code can be found in the standard library at https://golang.org/src/sort/sort.go#L53 ...