2017-02-12-shellsort-qsort.go

// This version of QuickSort reverts to InsertionSort
// when the slice size is below a cutoff value of 12.
// Add ShellSort before InsertionSort to help InsertionSort.
func QuickSort(data Interface, l int, r int, enableShellSort bool) {
  if l >= r {
    return
  }
  
  if r-l > 12 {
    pivot := partition(data, l, r)
    
    QuickSort(data, l, pivot-1, enableShellSort)
    QuickSort(data, pivot+1, r, enableShellSort)
  } else {
    if enableShellSort {
      // From Go source.
      // Do ShellSort pass with gap 6
      for i := l + 6; i < r; i++ {
        if data.Less(i, i-6) {
          data.Swap(i, i-6)
        }
      }
    }
    insertionSort(data, l, r)
  }
}