func TestShifts(t *testing.T) {
	data := make([]uint64, 10000)
	for i := range data {
		data[i] = 1 << uint((i*19)%64)
	}
	forceRadix(Uint64Slice(data).Sort)
	if !Uint64sAreSorted(data) {
		t.Errorf("shifts data didn't sort")
	}
}
TestShifts uses integer data consisting of a 1 bit in a random position.
It's like TestBrokenPrefix for integer data.
package sorts_test
import (
	"bytes"
	"fmt"
	"math/rand"
	"sort"
	"strconv"
	"testing"
	. "github.com/twotwotwo/sorts"
	. "github.com/twotwotwo/sorts/sortutil"
)
type unsortableInts struct{ IntSlice }
func (u unsortableInts) Less(i, j int) bool { return j&1 == 1 }
type unsortableUints struct{ UintSlice }
func (u unsortableUints) Less(i, j int) bool { return j&1 == 1 }
type unsortableStrings struct{ StringSlice }
func (u unsortableStrings) Less(i, j int) bool { return j&1 == 1 }
type unsortableBytes struct{ BytesSlice }
func (u unsortableBytes) Less(i, j int) bool { return j&1 == 1 }
type miskeyedInts struct{ IntSlice }
func (u miskeyedInts) Less(i, j int) bool { return u.IntSlice[j] < u.IntSlice[i] }
type miskeyedUints struct{ UintSlice }
func (u miskeyedUints) Less(i, j int) bool { return u.UintSlice[j] < u.UintSlice[i] }
type miskeyedStrings struct{ StringSlice }
func (u miskeyedStrings) Less(i, j int) bool { return u.StringSlice[j] < u.StringSlice[i] }
type miskeyedBytes struct{ BytesSlice }
func (u miskeyedBytes) Less(i, j int) bool {
	return bytes.Compare(u.BytesSlice[j], u.BytesSlice[i]) == -1
}
func mustPanic(t *testing.T, name string, f func()) {
	defer func() { _ = recover() }()
	f()
	t.Errorf("expected a panic on unsortable datatype %s", name)
}
func TestSortCheck(t *testing.T) {
	defer SetQSortCutoff(SetQSortCutoff(1))
	if !Checking() {
		return
	}
	mustPanic(t, "unsortableInts", func() {
		ByInt64(unsortableInts{IntSlice{1, 1, 1}})
	})
	mustPanic(t, "unsortableUints", func() {
		ByUint64(unsortableUints{UintSlice{1, 1, 1}})
	})
	mustPanic(t, "unsortableStrings", func() {
		ByString(unsortableStrings{StringSlice{"", "", ""}})
	})
	mustPanic(t, "unsortableBytes", func() {
		ByBytes(unsortableBytes{BytesSlice{[]byte{}, []byte{}, []byte{}}})
	})
	mustPanic(t, "miskeyedInts", func() {
		forceRadix(func() {
			ByInt64(miskeyedInts{IntSlice{1, 2, 3}})
		})
	})
	mustPanic(t, "miskeyedUints", func() {
		forceRadix(func() {
			ByUint64(miskeyedUints{UintSlice{1, 2, 3}})
		})
	})
	mustPanic(t, "miskeyedStrings", func() {
		forceRadix(func() {
			ByString(miskeyedStrings{StringSlice{"a", "b", "c"}})
		})
	})
	mustPanic(t, "miskeyedBytes", func() {
		forceRadix(func() {
			ByBytes(miskeyedBytes{BytesSlice{[]byte{'a'}, []byte{'b'}, []byte{'c'}}})
		})
	})
}
func TestFlip(t *testing.T) {
	data1, expected1 := [...]int{1, 2, 3, 4, 5}, [...]int{5, 4, 3, 2, 1}
	Flip(IntSlice(data1[:]))
	if data1 != expected1 {
		t.Errorf("Flip didn't flip!")
	}
	data2, expected2 := [...]int{1, 2}, [...]int{2, 1}
	Flip(IntSlice(data2[:]))
	if data2 != expected2 {
		t.Errorf("Flip didn't flip!")
	}
	Flip(IntSlice(nil))  
}
func TestEmpty(t *testing.T) {
	Quicksort(IntSlice(nil))
	IntSlice(nil).Sort()
	UintSlice(nil).Sort()
	StringSlice(nil).Sort()
	BytesSlice(nil).Sort()
	IntSlice(nil).Search(0)
	StringSlice(nil).Search("")
	BytesSlice(nil).Search([]byte(nil))
}
func TestTiny(t *testing.T) {
	Quicksort(IntSlice([]int{1}))
	IntSlice([]int{1}).Sort()
	UintSlice([]uint{1}).Sort()
	StringSlice([]string{""}).Sort()
	BytesSlice([][]byte{nil}).Sort()
	Quicksort(IntSlice([]int{1, 1}))
	IntSlice([]int{1, 1}).Sort()
	UintSlice([]uint{1, 1}).Sort()
	StringSlice([]string{"", ""}).Sort()
	BytesSlice([][]byte{nil, nil}).Sort()
}
func TestSortLarge_Random(t *testing.T) {
	n := 1000000
	if testing.Short() {
		n /= 100
	}
	data := make([]int, n)
	for i := 0; i < len(data); i++ {
		data[i] = rand.Intn(100)
	}
	if IntsAreSorted(data) {
		t.Fatalf("terrible rand.rand")
	}
	Ints(data)
	if !IntsAreSorted(data) {
		t.Errorf("sort didn't sort - 1M ints")
	}
}
type RoundedKeyInt64s struct { Int64Slice }
func (r RoundedKeyInt64s) Key(i int) int64 { return r.Int64Slice[i] / 10 }
type RoundedKeyUint64s struct { Uint64Slice }
func (r RoundedKeyUint64s) Key(i int) uint64 { return r.Uint64Slice[i] / 10 }
type TruncatedKeyStrings struct { StringSlice }
func (r TruncatedKeyStrings) Key(i int) string { return r.StringSlice[i][:1] }
type TruncatedKeyBytes struct { BytesSlice }
func (r TruncatedKeyBytes) Key(i int) []byte { return r.BytesSlice[i][:1] }
func TestTiebreakEqualKeys(t *testing.T) {
	n := 1000
	defer SetQSortCutoff(SetQSortCutoff(1))
	data := make([]int64, n)
	for i := 0; i < len(data); i++ {
		data[i] = rand.Int63n(100)
	}
	if Int64sAreSorted(data) {
		t.Errorf("no random test data")
	}
	ByInt64(RoundedKeyInt64s{Int64Slice(data)})
	if !Int64sAreSorted(data) {
		t.Errorf("sort didn't sort - 1K rounded ints")
	}
	uintData := make([]uint64, n)
	for i := 0; i < len(uintData); i++ {
		uintData[i] = uint64(rand.Int63n(100))
	}
	if Uint64sAreSorted(uintData) {
		t.Errorf("no random test data")
	}
	ByUint64(RoundedKeyUint64s{Uint64Slice(uintData)})
	if !Uint64sAreSorted(uintData) {
		t.Errorf("sort didn't sort - 1K rounded uints")
	}
	stringData := make([]string, n)
	for i := 0; i < len(stringData); i++ {
		stringData[i] = strconv.Itoa(rand.Intn(100))
	}
	if StringsAreSorted(stringData) {
		t.Errorf("no random test data")
	}
	ByString(TruncatedKeyStrings{StringSlice(stringData)})
	if !StringsAreSorted(stringData) {
		t.Errorf("sort didn't sort - 1K truncated strings")
	}
	bytesData := make([][]byte, n)
	for i := 0; i < len(bytesData); i++ {
		bytesData[i] = []byte(strconv.Itoa(rand.Intn(100)))
	}
	if BytesAreSorted(bytesData) {
		t.Errorf("no random test data")
	}
	ByBytes(TruncatedKeyBytes{BytesSlice(bytesData)})
	if !BytesAreSorted(bytesData) {
		t.Errorf("sort didn't sort - 1K truncated []bytes")
	}
}
func BenchmarkSortString1K(b *testing.B) {
	b.StopTimer()
	for i := 0; i < b.N; i++ {
		data := make([]string, 1<<10)
		for i := 0; i < len(data); i++ {
			data[i] = strconv.Itoa(i ^ 0x2cc)
		}
		b.StartTimer()
		Strings(data)
		b.StopTimer()
	}
}
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
		}
		b.StartTimer()
		Ints(data)
		b.StopTimer()
	}
}
func BenchmarkSortInt64K(b *testing.B) {
	b.StopTimer()
	for i := 0; i < b.N; i++ {
		data := make([]int, 1<<16)
		for i := 0; i < len(data); i++ {
			data[i] = i ^ 0xcccc
		}
		b.StartTimer()
		Ints(data)
		b.StopTimer()
	}
}
const (
	_Sawtooth = iota
	_Rand
	_Stagger
	_Plateau
	_Shuffle
	_NDist
)
const (
	_Copy = iota
	_Reverse
	_ReverseFirstHalf
	_ReverseSecondHalf
	_Sorted
	_Dither
	_NMode
)
type testingData struct {
	desc        string
	t           *testing.T
	data        []int
	maxswap     int  
	ncmp, nswap int
}
func (d *testingData) Len() int        { return len(d.data) }
func (d *testingData) Key(i int) int64 { return int64(d.data[i]) }
func (d *testingData) Less(i, j int) bool {
	d.ncmp++
	return d.data[i] < d.data[j]
}
func (d *testingData) Swap(i, j int) {
	if d.nswap >= d.maxswap {
		d.t.Errorf("%s: used %d swaps sorting slice of %d", d.desc, d.nswap, len(d.data))
		d.t.FailNow()
	}
	d.nswap++
	d.data[i], d.data[j] = d.data[j], d.data[i]
}
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
func lg(n int) int {
	i := 0
	for 1<<uint(i) < n {
		i++
	}
	return i
}
func testBentleyMcIlroy(t *testing.T, sort func(sort.Interface), maxswap func(int) int) {
	sizes := []int{100, 1023, 1024, 1025}
	if testing.Short() {
		sizes = []int{100, 127, 128, 129}
	}
	dists := []string{"sawtooth", "rand", "stagger", "plateau", "shuffle"}
	modes := []string{"copy", "reverse", "reverse1", "reverse2", "sort", "dither"}
	var tmp1, tmp2 [1025]int
	for _, n := range sizes {
		for m := 1; m < 2*n; m *= 2 {
			for dist := 0; dist < _NDist; dist++ {
				j := 0
				k := 1
				data := tmp1[0:n]
				for i := 0; i < n; i++ {
					switch dist {
					case _Sawtooth:
						data[i] = i % m
					case _Rand:
						data[i] = rand.Intn(m)
					case _Stagger:
						data[i] = (i*m + i) % n
					case _Plateau:
						data[i] = min(i, m)
					case _Shuffle:
						if rand.Intn(m) != 0 {
							j += 2
							data[i] = j
						} else {
							k += 2
							data[i] = k
						}
					}
				}
				mdata := tmp2[0:n]
				for mode := 0; mode < _NMode; mode++ {
					switch mode {
					case _Copy:
						for i := 0; i < n; i++ {
							mdata[i] = data[i]
						}
					case _Reverse:
						for i := 0; i < n; i++ {
							mdata[i] = data[n-i-1]
						}
					case _ReverseFirstHalf:
						for i := 0; i < n/2; i++ {
							mdata[i] = data[n/2-i-1]
						}
						for i := n / 2; i < n; i++ {
							mdata[i] = data[i]
						}
					case _ReverseSecondHalf:
						for i := 0; i < n/2; i++ {
							mdata[i] = data[i]
						}
						for i := n / 2; i < n; i++ {
							mdata[i] = data[n-(i-n/2)-1]
						}
					case _Sorted:
						for i := 0; i < n; i++ {
							mdata[i] = data[i]
						}
						Ints(mdata)
					case _Dither:
						for i := 0; i < n; i++ {
							mdata[i] = data[i] + i%5
						}
					}
					desc := fmt.Sprintf("n=%d m=%d dist=%s mode=%s", n, m, dists[dist], modes[mode])
					d := &testingData{desc: desc, t: t, data: mdata[0:n], maxswap: maxswap(n)}
					sort(d)
					if !IntsAreSorted(mdata) {
						t.Errorf("%s: ints not sorted", desc)
						t.Errorf("\t%v", mdata)
						t.FailNow()
					}
				}
			}
		}
	}
}
func byInt64Wrapper(d sort.Interface) {
	ByInt64(d.(Int64Interface))
}
func TestSortBM(t *testing.T) {
	testBentleyMcIlroy(t, byInt64Wrapper, func(n int) int { return n * lg(n) * 12 / 10 })
}
func TestManySortBM(t *testing.T) {
	testBentleyMcIlroy(t, manySortWrapper, func(n int) int { return n * lg(n) * 12 / 10 })
}
func TestHeapsortBM(t *testing.T) {
	testBentleyMcIlroy(t, Heapsort, func(n int) int { return n * lg(n) * 12 / 10 })
}
func TestBackshift(t *testing.T) {
	funnyData := [1e3]int{1: -1}
	funny := IntSlice(funnyData[:])
	if GuessIntShift(funny, len(funny)) > 0 {
		panic("guessIntShift got smarter")
	}
	forceRadix(func() { multiSort(funnyData[:]) })
	if !sort.IsSorted(funny) {
		t.Errorf("backshift data didn't sort")
	}
}
func TestFwdShift(t *testing.T) {
	funnyData := []int{0x40000000, 23, 59, 38, 38, 6, 12, 9, 3, 4, 1, 49, 9, 63}
	funny := IntSlice(funnyData)
	forceRadix(func() { multiSort(funnyData) })
	if !sort.IsSorted(funny) {
		t.Errorf("forward-shift data didn't sort")
	}
}
func TestBrokenPrefix(t *testing.T) {
	src := [128]byte{}
	src[64] = 1
	data := [10000][]byte{}
	for i := range data {
		data[i] = src[:]
	}
	for i := 10000 - 64; i < 10000; i++ {
		data[i] = src[64-((i*11)%64):]
	}
	forceRadix(BytesSlice(data[:]).Sort)
	if !BytesAreSorted(data[:]) {
		t.Errorf("broken-prefix data didn't sort")
	}
	srcStr := string(src[:])
	dataStr := [10000]string{}
	for i := range dataStr {
		dataStr[i] = srcStr
	}
	for i := 10000 - 64; i < 10000; i++ {
		data[i] = src[64-((i*11)%64):]
	}
	forceRadix(StringSlice(dataStr[:]).Sort)
	if !StringsAreSorted(dataStr[:]) {
		t.Errorf("broken-prefix data didn't sort")
	}
}