Overhead of stable sorting, in Go

stablesort_test.go

package stablesort

import (
	"math/rand"
	"sort"
	"testing"

	"golang.org/x/exp/slices"
)

const (
	M    = 500
	SIZE = 1000
)

func TestSlice(t *testing.T) {
	r := rand.New(rand.NewSource(42))
	data := randData(r)

	comparisons := 0
	for k := range data {
		sort.Slice(data[k], func(i, j int) bool {
			comparisons++
			return data[k][i] < data[k][j]
		})
	}
	t.Logf("sort.Slice: %d comparisons", comparisons)
}

func TestSliceStable(t *testing.T) {
	r := rand.New(rand.NewSource(42))
	data := randData(r)

	comparisons := 0
	for k := range data {
		sort.SliceStable(data[k], func(i, j int) bool {
			comparisons++
			return data[k][i] < data[k][j]
		})
	}
	t.Logf("sort.SliceStable: %d comparisons", comparisons)
}

func TestSortFunc(t *testing.T) {
	r := rand.New(rand.NewSource(42))
	data := randData(r)

	comparisons := 0
	for k := range data {
		slices.SortFunc(data[k], func(a, b rune) bool {
			comparisons++
			return a < b
		})
	}
	t.Logf("slices.SortFunc: %d comparisons", comparisons)
}

func TestSortStableFunc(t *testing.T) {
	r := rand.New(rand.NewSource(42))
	data := randData(r)

	comparisons := 0
	for k := range data {
		slices.SortStableFunc(data[k], func(a, b rune) bool {
			comparisons++
			return a < b
		})
	}
	t.Logf("slices.SortStableFunc: %d comparisons", comparisons)
}

func randLetter(r *rand.Rand) rune {
	return 'a' + rune(r.Intn(26))
}

func randData(r *rand.Rand) [][]rune {
	data := make([][]rune, M)
	for i := range data {
		data[i] = make([]rune, SIZE)
		for j := range data[i] {
			data[i][j] = randLetter(r)
		}
	}
	return data
}

func TestData(t *testing.T) {
	r := rand.New(rand.NewSource(42))
	data := randData(r)
	t.Log(string(data[0][:60])) // Okay this looks like "hrukpttuezptneuvunhuksqvgzadxlgghejkmvezjpmkqakmtrgkfbswyjun"
}

    stablesort_test.go:27: sort.Slice: 3203928 comparisons
    stablesort_test.go:41: sort.SliceStable: 5340823 comparisons
    stablesort_test.go:55: slices.SortFunc: 3203928 comparisons
    stablesort_test.go:69: slices.SortStableFunc: 5340823 comparisons