Hands-On High Performance with Go

Merge sort

Merge sort is a sorting algorithm with an O(n log n) average time complexity. MergeSort is often used if the goal of the algorithm is to produce a stable sort. A stable sort ensures that two objects that share the same key in an input array appear in the resulting array in the same order. Stability is important if we want to make sure that a key-value order pair is organized within an array. An implementation of a stable sort can be found in the Go standard library. This can be seen in the following code snippet:

func stable(data Interface, n int) {  blockSize := 20 // must be > 0  a, b := 0, blockSize  for b <= n {    insertionSort(data, a, b)    a = b    b += blockSize  }  insertionSort(data, a, n)  for blockSize < n { a, b = 0, 2*blockSize ...