Interface Performance

mysort.go

package mysort

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func insertionSort(data []int, a, b int) {
	for i := a + 1; i < b; i++ {
		for j := i; j > a && (data[j] < data[j-1]); j-- {
			data[j], data[j-1] = data[j-1], data[j]
		}
	}
}

func siftDown(data []int, lo, hi, first int) {
	root := lo
	for {
		child := 2*root + 1
		if child >= hi {
			break
		}
		if child+1 < hi && (data[first+child] < data[first+child+1]) {
			child++
		}
		if !(data[first+root] < data[first+child]) {
			return
		}
		data[first+root], data[first+child] = data[first+child], data[first+root]
		root = child
	}
}

func heapSort(data []int, a, b int) {
	first := a
	lo := 0
	hi := b - a
	for i := (hi - 1) / 2; i >= 0; i-- {
		siftDown(data, i, hi, first)
	}
	for i := hi - 1; i >= 0; i-- {
		data[first], data[first+i] = data[first+i], data[first]
		siftDown(data, lo, i, first)
	}
}

func medianOfThree(data []int, a, b, c int) {
	m0 := b
	m1 := a
	m2 := c
	if data[m1] < data[m0] {
		data[m1], data[m0] = data[m0], data[m1]
	}
	if data[m2] < data[m1] {
		data[m2], data[m1] = data[m1], data[m2]
	}
	if data[m1] < data[m0] {
		data[m1], data[m0] = data[m0], data[m1]
	}
}

func swapRange(data []int, a, b, n int) {
	for i := 0; i < n; i++ {
		data[a+i], data[b+i] = data[b+i], data[a+i]
	}
}

func doPivot(data []int, lo, hi int) (midlo, midhi int) {
	m := lo + (hi-lo)/2 // Written like this to avoid integer overflow.
	if hi-lo > 40 {
		s := (hi - lo) / 8
		medianOfThree(data, lo, lo+s, lo+2*s)
		medianOfThree(data, m, m-s, m+s)
		medianOfThree(data, hi-1, hi-1-s, hi-1-2*s)
	}
	medianOfThree(data, lo, m, hi-1)
	pivot := lo
	a, b, c, d := lo+1, lo+1, hi, hi
	for {
		for b < c {
			if data[b] < data[pivot] { // data[b] < pivot
				b++
			} else if !(data[pivot] < data[b]) { // data[b] = pivot
				data[a], data[b] = data[b], data[a]
				a++
				b++
			} else {
				break
			}
		}
		for b < c {
			if data[pivot] < data[c-1] { // data[c-1] > pivot
				c--
			} else if !(data[c-1] < data[pivot]) { // data[c-1] = pivot
				data[c-1], data[d-1] = data[d-1], data[c-1]
				c--
				d--
			} else {
				break
			}
		}
		if b >= c {
			break
		}
		data[b], data[c-1] = data[c-1], data[b]
		b++
		c--
	}
	n := min(b-a, a-lo)
	swapRange(data, lo, b-n, n)
	n = min(hi-d, d-c)
	swapRange(data, c, hi-n, n)
	return lo + b - a, hi - (d - c)
}

func quickSort(data []int, a, b, maxDepth int) {
	for b-a > 7 {
		if maxDepth == 0 {
			heapSort(data, a, b)
			return
		}
		maxDepth--
		mlo, mhi := doPivot(data, a, b)
		if mlo-a < b-mhi {
			quickSort(data, a, mlo, maxDepth)
			a = mhi // i.e., quickSort(data, mhi, b)
		} else {
			quickSort(data, mhi, b, maxDepth)
			b = mlo // i.e., quickSort(data, a, mlo)
		}
	}
	if b-a > 1 {
		insertionSort(data, a, b)
	}
}

func MyIntSort(data []int) {
	n := len(data)
	maxDepth := 0
	for i := n; i > 0; i >>= 1 {
		maxDepth++
	}
	maxDepth *= 2
	quickSort(data, 0, n, maxDepth)
}

mysort_func.go

package mysort

func insertionSortFunc(data []int, a, b int) {
	for i := a + 1; i < b; i++ {
		for j := i; j > a && Less(data, j, j-1); j-- {
			Swap(data, j, j-1)
		}
	}
}

func siftDownFunc(data []int, lo, hi, first int) {
	root := lo
	for {
		child := 2*root + 1
		if child >= hi {
			break
		}
		if child+1 < hi && Less(data, first+child, first+child+1) {
			child++
		}
		if !Less(data, first+root, first+child) {
			return
		}
		Swap(data, first+root, first+child)
		root = child
	}
}

func heapSortFunc(data []int, a, b int) {
	first := a
	lo := 0
	hi := b - a
	for i := (hi - 1) / 2; i >= 0; i-- {
		siftDownFunc(data, i, hi, first)
	}
	for i := hi - 1; i >= 0; i-- {
		Swap(data, first, first+i)
		siftDownFunc(data, lo, i, first)
	}
}

func medianOfThreeFunc(data []int, a, b, c int) {
	m0 := b
	m1 := a
	m2 := c
	if Less(data, m1, m0) {
		Swap(data, m1, m0)
	}
	if Less(data, m2, m1) {
		Swap(data, m2, m1)
	}
	if Less(data, m1, m0) {
		Swap(data, m1, m0)
	}
}

func swapRangeFunc(data []int, a, b, n int) {
	for i := 0; i < n; i++ {
		Swap(data, a+i, b+i)
	}
}

func doPivotFunc(data []int, lo, hi int) (midlo, midhi int) {
	m := lo + (hi-lo)/2 // Written like this to avoid integer overflow.
	if hi-lo > 40 {
		s := (hi - lo) / 8
		medianOfThreeFunc(data, lo, lo+s, lo+2*s)
		medianOfThreeFunc(data, m, m-s, m+s)
		medianOfThreeFunc(data, hi-1, hi-1-s, hi-1-2*s)
	}
	medianOfThreeFunc(data, lo, m, hi-1)
	pivot := lo
	a, b, c, d := lo+1, lo+1, hi, hi
	for {
		for b < c {
			if Less(data, b, pivot) { // data[b] < pivot
				b++
			} else if !Less(data, pivot, b) { // data[b] = pivot
				Swap(data, a, b)
				a++
				b++
			} else {
				break
			}
		}
		for b < c {
			if Less(data, pivot, c-1) { // data[c-1] > pivot
				c--
			} else if !Less(data, c-1, pivot) { // data[c-1] = pivot
				Swap(data, c-1, d-1)
				c--
				d--
			} else {
				break
			}
		}
		if b >= c {
			break
		}
		Swap(data, b, c-1)
		b++
		c--
	}
	n := min(b-a, a-lo)
	swapRangeFunc(data, lo, b-n, n)
	n = min(hi-d, d-c)
	swapRangeFunc(data, c, hi-n, n)
	return lo + b - a, hi - (d - c)
}

func quickSortFunc(data []int, a, b, maxDepth int) {
	for b-a > 7 {
		if maxDepth == 0 {
			heapSortFunc(data, a, b)
			return
		}
		maxDepth--
		mlo, mhi := doPivotFunc(data, a, b)
		if mlo-a < b-mhi {
			quickSortFunc(data, a, mlo, maxDepth)
			a = mhi // i.e., quickSort(data, mhi, b)
		} else {
			quickSortFunc(data, mhi, b, maxDepth)
			b = mlo // i.e., quickSort(data, a, mlo)
		}
	}
	if b-a > 1 {
		insertionSortFunc(data, a, b)
	}
}

func MyIntSortFunc(data []int) {
	n := Len(data)
	maxDepth := 0
	for i := n; i > 0; i >>= 1 {
		maxDepth++
	}
	maxDepth *= 2
	quickSortFunc(data, 0, n, maxDepth)
}

func Len(data []int) int {
	return len(data)
}

func Less(data []int, i, j int) bool {
	return data[i] < data[j]
}

func Swap(data []int, i, j int) {
	data[i], data[j] = data[j], data[i]
}

mysort_ptr.go

package mysort

type IntSlicePtr struct {
	data []int
}

func (is *IntSlicePtr) Len() int {
	return len(is.data)
}

func (is *IntSlicePtr) Less(i, j int) bool {
	return is.data[i] < is.data[j]
}

func (is *IntSlicePtr) Swap(i, j int) {
	is.data[i], is.data[j] = is.data[j], is.data[i]
}

func insertionSortPtr(data *IntSlicePtr, a, b int) {
	for i := a + 1; i < b; i++ {
		for j := i; j > a && data.Less(j, j-1); j-- {
			data.Swap(j, j-1)
		}
	}
}

func siftDownPtr(data *IntSlicePtr, lo, hi, first int) {
	root := lo
	for {
		child := 2*root + 1
		if child >= hi {
			break
		}
		if child+1 < hi && data.Less(first+child, first+child+1) {
			child++
		}
		if !data.Less(first+root, first+child) {
			return
		}
		data.Swap(first+root, first+child)
		root = child
	}
}

func heapSortPtr(data *IntSlicePtr, a, b int) {
	first := a
	lo := 0
	hi := b - a
	for i := (hi - 1) / 2; i >= 0; i-- {
		siftDownPtr(data, i, hi, first)
	}
	for i := hi - 1; i >= 0; i-- {
		data.Swap(first, first+i)
		siftDownPtr(data, lo, i, first)
	}
}

func medianOfThreePtr(data *IntSlicePtr, a, b, c int) {
	m0 := b
	m1 := a
	m2 := c
	if data.Less(m1, m0) {
		data.Swap(m1, m0)
	}
	if data.Less(m2, m1) {
		data.Swap(m2, m1)
	}
	if data.Less(m1, m0) {
		data.Swap(m1, m0)
	}
}

func swapRangePtr(data *IntSlicePtr, a, b, n int) {
	for i := 0; i < n; i++ {
		data.Swap(a+i, b+i)
	}
}

func doPivotPtr(data *IntSlicePtr, lo, hi int) (midlo, midhi int) {
	m := lo + (hi-lo)/2 // Written like this to avoid integer overflow.
	if hi-lo > 40 {
		s := (hi - lo) / 8
		medianOfThreePtr(data, lo, lo+s, lo+2*s)
		medianOfThreePtr(data, m, m-s, m+s)
		medianOfThreePtr(data, hi-1, hi-1-s, hi-1-2*s)
	}
	medianOfThreePtr(data, lo, m, hi-1)
	pivot := lo
	a, b, c, d := lo+1, lo+1, hi, hi
	for {
		for b < c {
			if data.Less(b, pivot) { // data[b] < pivot
				b++
			} else if !data.Less(pivot, b) { // data[b] = pivot
				data.Swap(a, b)
				a++
				b++
			} else {
				break
			}
		}
		for b < c {
			if data.Less(pivot, c-1) { // data[c-1] > pivot
				c--
			} else if !data.Less(c-1, pivot) { // data[c-1] = pivot
				data.Swap(c-1, d-1)
				c--
				d--
			} else {
				break
			}
		}
		if b >= c {
			break
		}
		data.Swap(b, c-1)
		b++
		c--
	}
	n := min(b-a, a-lo)
	swapRangePtr(data, lo, b-n, n)
	n = min(hi-d, d-c)
	swapRangePtr(data, c, hi-n, n)
	return lo + b - a, hi - (d - c)
}

func quickSortPtr(data *IntSlicePtr, a, b, maxDepth int) {
	for b-a > 7 {
		if maxDepth == 0 {
			heapSortPtr(data, a, b)
			return
		}
		maxDepth--
		mlo, mhi := doPivotPtr(data, a, b)
		if mlo-a < b-mhi {
			quickSortPtr(data, a, mlo, maxDepth)
			a = mhi // i.e., quickSort(data, mhi, b)
		} else {
			quickSortPtr(data, mhi, b, maxDepth)
			b = mlo // i.e., quickSort(data, a, mlo)
		}
	}
	if b-a > 1 {
		insertionSortPtr(data, a, b)
	}
}

func MyIntSortPtr(data *IntSlicePtr) {
	n := data.Len()
	maxDepth := 0
	for i := n; i > 0; i >>= 1 {
		maxDepth++
	}
	maxDepth *= 2
	quickSortPtr(data, 0, n, maxDepth)
}

mysort_struct.go

package mysort

type IntSlice struct {
	data []int
}

func (is IntSlice) Len() int {
	return len(is.data)
}

func (is IntSlice) Less(i, j int) bool {
	return is.data[i] < is.data[j]
}

func (is IntSlice) Swap(i, j int) {
	is.data[i], is.data[j] = is.data[j], is.data[i]
}

func insertionSortStruct(data IntSlice, a, b int) {
	for i := a + 1; i < b; i++ {
		for j := i; j > a && data.Less(j, j-1); j-- {
			data.Swap(j, j-1)
		}
	}
}

func siftDownStruct(data IntSlice, lo, hi, first int) {
	root := lo
	for {
		child := 2*root + 1
		if child >= hi {
			break
		}
		if child+1 < hi && data.Less(first+child, first+child+1) {
			child++
		}
		if !data.Less(first+root, first+child) {
			return
		}
		data.Swap(first+root, first+child)
		root = child
	}
}

func heapSortStruct(data IntSlice, a, b int) {
	first := a
	lo := 0
	hi := b - a
	for i := (hi - 1) / 2; i >= 0; i-- {
		siftDownStruct(data, i, hi, first)
	}
	for i := hi - 1; i >= 0; i-- {
		data.Swap(first, first+i)
		siftDownStruct(data, lo, i, first)
	}
}

func medianOfThreeStruct(data IntSlice, a, b, c int) {
	m0 := b
	m1 := a
	m2 := c
	if data.Less(m1, m0) {
		data.Swap(m1, m0)
	}
	if data.Less(m2, m1) {
		data.Swap(m2, m1)
	}
	if data.Less(m1, m0) {
		data.Swap(m1, m0)
	}
}

func swapRangeStruct(data IntSlice, a, b, n int) {
	for i := 0; i < n; i++ {
		data.Swap(a+i, b+i)
	}
}

func doPivotStruct(data IntSlice, lo, hi int) (midlo, midhi int) {
	m := lo + (hi-lo)/2 // Written like this to avoid integer overflow.
	if hi-lo > 40 {
		s := (hi - lo) / 8
		medianOfThreeStruct(data, lo, lo+s, lo+2*s)
		medianOfThreeStruct(data, m, m-s, m+s)
		medianOfThreeStruct(data, hi-1, hi-1-s, hi-1-2*s)
	}
	medianOfThreeStruct(data, lo, m, hi-1)
	pivot := lo
	a, b, c, d := lo+1, lo+1, hi, hi
	for {
		for b < c {
			if data.Less(b, pivot) { // data[b] < pivot
				b++
			} else if !data.Less(pivot, b) { // data[b] = pivot
				data.Swap(a, b)
				a++
				b++
			} else {
				break
			}
		}
		for b < c {
			if data.Less(pivot, c-1) { // data[c-1] > pivot
				c--
			} else if !data.Less(c-1, pivot) { // data[c-1] = pivot
				data.Swap(c-1, d-1)
				c--
				d--
			} else {
				break
			}
		}
		if b >= c {
			break
		}
		data.Swap(b, c-1)
		b++
		c--
	}
	n := min(b-a, a-lo)
	swapRangeStruct(data, lo, b-n, n)
	n = min(hi-d, d-c)
	swapRangeStruct(data, c, hi-n, n)
	return lo + b - a, hi - (d - c)
}

func quickSortStruct(data IntSlice, a, b, maxDepth int) {
	for b-a > 7 {
		if maxDepth == 0 {
			heapSortStruct(data, a, b)
			return
		}
		maxDepth--
		mlo, mhi := doPivotStruct(data, a, b)
		if mlo-a < b-mhi {
			quickSortStruct(data, a, mlo, maxDepth)
			a = mhi // i.e., quickSort(data, mhi, b)
		} else {
			quickSortStruct(data, mhi, b, maxDepth)
			b = mlo // i.e., quickSort(data, a, mlo)
		}
	}
	if b-a > 1 {
		insertionSortStruct(data, a, b)
	}
}

func MyIntSortStruct(data IntSlice) {
	n := data.Len()
	maxDepth := 0
	for i := n; i > 0; i >>= 1 {
		maxDepth++
	}
	maxDepth *= 2
	quickSortStruct(data, 0, n, maxDepth)
}

mysort_test.go

package mysort

import (
	"sort"
	"testing"
)

var ints = [...]int{
	74, 59, 238, -784, 9845, 959, 905, 0, 0, 42, 7586, -5467984, 7586,
}

func TestMyIntSort(t *testing.T) {
	data := ints
	a := data[0:]
	MyIntSort(a)
	if !sort.IsSorted(sort.IntSlice(a)) {
		t.Errorf("sorted %v", ints)
		t.Errorf("   got %v", data)
	}
}

func TestMyIntSortFunc(t *testing.T) {
	data := ints
	a := data[0:]
	MyIntSortFunc(a)
	if !sort.IsSorted(sort.IntSlice(a)) {
		t.Errorf("sorted %v", ints)
		t.Errorf("   got %v", data)
	}
}

func TestMyIntSortStruct(t *testing.T) {
	data := ints
	a := data[0:]
	MyIntSortStruct(IntSlice{a})
	if !sort.IsSorted(sort.IntSlice(a)) {
		t.Errorf("sorted %v", ints)
		t.Errorf("   got %v", data)
	}
}

func TestMyIntSortPtr(t *testing.T) {
	data := ints
	a := data[0:]
	MyIntSortPtr(&IntSlicePtr{a})
	if !sort.IsSorted(sort.IntSlice(a)) {
		t.Errorf("sorted %v", ints)
		t.Errorf("   got %v", data)
	}
}

func BenchmarkSortInt1K(b *testing.B) {
	b.StopTimer()
	for i := 0; i < b.N; i++ {
		data := make([]int, 1<<10)
		for i := 0; i < len(data); i++ {
			data[i] = i ^ 0x2cc
		}
		d := sort.IntSlice(data)
		b.StartTimer()
		sort.Sort(d)
		b.StopTimer()
	}
}

func BenchmarkMyIntSort1K(b *testing.B) {
	b.StopTimer()
	for i := 0; i < b.N; i++ {
		data := make([]int, 1<<10)
		for i := 0; i < len(data); i++ {
			data[i] = i ^ 0x2cc
		}
		b.StartTimer()
		MyIntSort(data)
		b.StopTimer()
	}
}

func BenchmarkMyIntSortFunc1K(b *testing.B) {
	b.StopTimer()
	for i := 0; i < b.N; i++ {
		data := make([]int, 1<<10)
		for i := 0; i < len(data); i++ {
			data[i] = i ^ 0x2cc
		}
		b.StartTimer()
		MyIntSortFunc(data)
		b.StopTimer()
	}
}

func BenchmarkMyIntSortStruct1k(b *testing.B) {
	b.StopTimer()
	for i := 0; i < b.N; i++ {
		data := make([]int, 1<<10)
		for i := 0; i < len(data); i++ {
			data[i] = i ^ 0x2cc
		}
		d := IntSlice{data}
		b.StartTimer()
		MyIntSortStruct(d)
		b.StopTimer()
	}
}

func BenchmarkMyIntSortPtr1k(b *testing.B) {
	b.StopTimer()
	for i := 0; i < b.N; i++ {
		data := make([]int, 1<<10)
		for i := 0; i < len(data); i++ {
			data[i] = i ^ 0x2cc
		}
		d := &IntSlicePtr{data}
		b.StartTimer()
		MyIntSortPtr(d)
		b.StopTimer()
	}
}

output.sh

$ go test -bench .
PASS
BenchmarkSortInt1K-8	   10000	    150809 ns/op
BenchmarkMyIntSort1K-8	   50000	     34777 ns/op
BenchmarkMyIntSortFunc1K-8	   50000	     51170 ns/op
BenchmarkMyIntSortStruct1k-8	   10000	    143204 ns/op
BenchmarkMyIntSortPtr1k-8	   50000	     56585 ns/op
ok  	_/home/jmarsh/sort_test/mysort	13.993s