dual pivot quicksort is about 10% faster than classic quicksort

quicksort.go

// quicksort
package main
 
import (
	"fmt"
	"math/rand"
	"sort"
	"time"
)
 
// classic quicksort
func quicksort(lo, hi int, arr []int) {
	if hi-lo < 2 {
		return
	}
 
	m := arr[hi-1]
	a := lo
	for b := lo; b < hi-1; b++ {
		if arr[b] < m {
			arr[a], arr[b] = arr[b], arr[a]
			a++
		}
	}
 
	arr[a], arr[hi-1] = m, arr[a]
 
	quicksort(lo, a, arr)
	quicksort(a+1, hi, arr)
}
 
// less swap
func quicksort2(lo, hi int, arr []int) {
	if hi-lo < 3 {
		if hi != lo && arr[lo] > arr[hi-1] {
			arr[lo], arr[hi-1] = arr[hi-1], arr[lo]
		}
		return
	}
 
	arr[(lo+hi)/2], arr[hi-1] = arr[hi-1], arr[(lo+hi)/2]
	m := arr[hi-1]
	a, b := lo, hi-2
	for {
		for arr[a] < m {
			a++
		}
		for arr[b] >= m && a < b {
			b--
		}
		if a >= b {
			break
		}
		arr[a], arr[b] = arr[b], arr[a]
	}
 
	arr[a], arr[hi-1] = m, arr[a]
 
	quicksort2(lo, a, arr)
	quicksort2(a+1, hi, arr)
}
 
// dual pivot quicksort
// http://iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf
func quicksort3(lo, hi int, arr []int) {
	if hi-lo < 3 {
		if hi != lo && arr[lo] > arr[hi-1] {
			arr[lo], arr[hi-1] = arr[hi-1], arr[lo]
		}
		return
	}
 
	p1, p2 := arr[lo], arr[hi-1]
	if p1 > p2 {
		p1, p2 = p2, p1
		arr[lo], arr[hi-1] = p1, p2
	}
 
	a, b := lo, hi-1
	for i := lo + 1; i < b; {
		if arr[i] < p1 {
			a++
			arr[a], arr[i] = arr[i], arr[a]
			i++
		} else if arr[i] > p2 {
			b--
			arr[b], arr[i] = arr[i], arr[b]
		} else {
			i++
		}
	}
 
	arr[a], arr[lo] = arr[lo], arr[a]
	arr[b], arr[hi-1] = arr[hi-1], arr[b]
 
	quicksort3(lo, a, arr)
	quicksort3(a+1, b, arr)
	quicksort3(b+1, hi, arr)
}
 
func main() {
	n1, n2 := 100, 100000
	a := make([][]int, n1)
	b := make([][]int, n1)
	c := make([][]int, n1)
	d := make([][]int, n1)
 
	for i := range a {
		a[i] = make([]int, n2)
		b[i] = make([]int, n2)
		c[i] = make([]int, n2)
		d[i] = make([]int, n2)
		for j := range a[i] {
			a[i][j] = rand.Int()
		}
		copy(b[i], a[i])
		copy(c[i], a[i])
		copy(d[i], a[i])
	}
 
	t := time.Now()
	for i := range a {
		quicksort(0, n2, a[i])
	}
	fmt.Println(time.Since(t))
 
	t = time.Now()
	for i := range b {
		quicksort2(0, n2, b[i])
	}
	fmt.Println(time.Since(t))
 
	t = time.Now()
	for i := range c {
		quicksort3(0, n2, c[i])
	}
	fmt.Println(time.Since(t))
 
	t = time.Now()
	for i := range d {
		sort.Ints(d[i])
	}
	fmt.Println(time.Since(t))
 
	// check sort result
	for i := range a {
		for j := range a[i] {
			if a[i][j] != d[i][j] || b[i][j] != d[i][j] || c[i][j] != d[i][j] {
				fmt.Println(i, j, a[i][j], b[i][j], c[i][j], d[i][j])
				break
			}
		}
 
	}
}