How much overhead for a STABLE sort of 1000 lowercase letters (26 possible values per letter), compared to a standard sort?

stablesort_test.go

package stablesort

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

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 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:25: sort.Slice: 3203928 comparisons
    stablesort_test.go:39: sort.SliceStable: 5340823 comparisons

-> 66% overhead in number of comparisons, when calling sort.SliceStable.