The difference seems to largely be due to the fact that your Quicksort uses builtins. It slices and uses len
. Keep in mind that sort.Sort
takes in a sort.Interface
. So every time you call len
it calls slice.Len
and every time you do array[i],array[j] = array[j],array[i]
it has to call Swap(i,j)
.
I wrote a comparable version that works on an arbitrary qsort.Interface
:
func Qsort(a Interface, prng *rand.Rand) Interface {
if a.Len() < 2 {
return a
}
left, right := 0, a.Len()-1
// Pick a pivot
pivotIndex := prng.Int() % a.Len()
// Move the pivot to the right
a.Swap(pivotIndex, right)
// Pile elements smaller than the pivot on the left
for i := 0; i < a.Len(); i++ {
if a.Less(i, right) {
a.Swap(i, left)
left++
}
}
// Place the pivot after the last smaller element
a.Swap(left, right)
// Go down the rabbit hole
leftSide, rightSide := a.Partition(left)
Qsort(leftSide, prng)
Qsort(rightSide, prng)
return a
}
Then I used Go's benchmark functionality (which you should always use for Benchmarks where possible).
For reference and transparency, qsort.Interface
is defined as:
type Interface interface {
sort.Interface
// Partition returns slice[:i] and slice[i+1:]
// These should references the original memory
// since this does an in-place sort
Partition(i int) (left Interface, right Interface)
}
The actual IntSlice
implementation for qsort
is:
type IntSlice []int
func (is IntSlice) Less(i, j int) bool {
return is[i] < is[j]
}
func (is IntSlice) Swap(i, j int) {
is[i], is[j] = is[j], is[i]
}
func (is IntSlice) Len() int {
return len(is)
}
func (is IntSlice) Partition(i int) (left Interface, right Interface) {
return IntSlice(is[:i]), IntSlice(is[i+1:])
}
Finally, here's the qsort_test.go
file:
package qsort_test
import (
"math/rand"
"qsort"
"sort"
"testing"
"time"
)
const size int = 1000000
var list = make([]int, size)
var prng = rand.New(rand.NewSource(int64(time.Now().Nanosecond())))
func BenchmarkQsort(b *testing.B) {
for n := 0; n < b.N; n++ {
b.StopTimer()
for i := range list {
list[i] = prng.Int()
}
b.StartTimer()
qsort.Qsort(qsort.IntSlice(list), prng)
}
}
func BenchmarkNativeQsort(b *testing.B) {
for n := 0; n < b.N; n++ {
b.StopTimer()
for i := range list {
list[i] = prng.Int()
}
b.StartTimer()
qsort.NativeQsort(list, prng)
}
}
func BenchmarkSort(b *testing.B) {
for n := 0; n < b.N; n++ {
b.StopTimer()
for i := range list {
list[i] = prng.Int()
}
b.StartTimer()
sort.Sort(sort.IntSlice(list))
}
}
The results (formatting mine):
PASS
BenchmarkQsort 5 513629360 ns/op
BenchmarkNativeQsort 10 160609180 ns/op
BenchmarkSort 5 292416760 ns/op
As you can see, the standard library's sort massively outperforms your qsort on average with random data. NativeQsort
refers to the qsort
functions you posted in your actual question, and it outperforms both. The only thing that's changed between that and Qsort
is that I swapped the builtin functions for qsort.Interface
. It follows, then, that genericity is likely the reason one is slower than the other.
Edit: There aren't many samples because of how expensive sorting is, so here are the results with -benchtime 10s
just for slightly more representative results.
BenchmarkQsort 50 524389994 ns/op
BenchmarkNativeQsort 100 161199217 ns/op
BenchmarkSort 50 302037284 ns/op