2017-02-12-media-of-3-qsort.go

// This version of partition uses as media-of-three pivot
// instead of a randomized pivot.
func partition(data Interface, l, r int) int {
  m := l + (r-l)/2             // Avoid integer overflow
  medianOfThree(data, l, m, r) // Pivot is placed at l

  i := l + 1
  for j := l + 1; j <= r; j++ {
    if data.Less(j, l) {
      if i != j {
        data.Swap(i, j)
      }
      i++
    }
  }
  data.Swap(l, i-1)
  return i - 1
}

// Taken from Go source
func medianOfThree(data Interface, m1, m0, m2 int) {
  // sort 3 elements
  if data.Less(m1, m0) {
    data.Swap(m1, m0)
  }
  // data[m0] <= data[m1]
  if data.Less(m2, m1) {
    data.Swap(m2, m1)
    // data[m0] <= data[m2] && data[m1] < data[m2]
    if data.Less(m1, m0) {
      data.Swap(m1, m0)
    }
  }
  // now data[m0] <= data[m1] <= data[m2]
}