sorty

README

sorty

sorty is a type-specific, fast, efficient, concurrent/parallel QuickSort implementation (with an improved InsertionSort as subroutine). It is in-place and does not require extra memory (other than efficient recursive calls and goroutines). You can call corresponding Sort*() to rapidly sort your slices (in ascending order) or collections of objects. For example:

sorty.SortS(string_slice) // native slice
sorty.Sort(n, lesswap)    // lesswap() function based

If you have a pair of Less() and Swap(), then you can trivially write your lesswap() and sort your generic collections using multiple CPU cores quickly. sorty natively sorts [][]byte,[]float32,[]float64,[]int,[]int32,[]int64, []uintptr,[]string,[]uint,[]uint32,[]uint64. sorty also natively sorts []string and [][]T (for any type T) by length.

sorty is stable (as in version), well-tested and pretty careful with resources & performance:

• lesswap() operates faster than sort.Interface on generic collections.
• For each Sort*() call, sorty uses up to Mxg (3 by default, including caller) concurrent goroutines and up to one channel.
• Goroutines and channel are created/used only when necessary.
• Mxg=1 (or a short input) yields single-goroutine sorting: No goroutines or channel will be created.
• Mxg can be changed live, even during an ongoing Sort*() call.
• Mli,Hmli,Mlr parameters are tuned to get the best performance, see below.
• sorty API adheres to semantic versioning.

Benchmarks

Comparing against sort.Slice, sortutil, zermelo and radix with Go version 1.17.1 on:

Machine	CPU	OS	Kernel
R	Ryzen 1600	Manjaro	5.10.68
X	Xeon Broadwell	Ubuntu 20.04	5.11.0-1020-gcp
i5	Core i5 4210M	Manjaro	5.10.68

Sorting uniformly distributed random uint32 slice (in seconds):

Library(-Mxg)	R	X	i5
sort.Slice	12.18	16.78	13.98
sortutil	1.48	3.42	3.10
zermelo	2.10	1.83	1.12
sorty-1	5.83	7.92	6.06
sorty-2	3.07	4.00	3.17
sorty-3	2.30	3.29	2.62
sorty-4	1.82	2.82	2.27
sortyLsw-1	11.39	14.71	12.90
sortyLsw-2	6.02	7.49	6.78
sortyLsw-3	4.20	5.96	5.21
sortyLsw-4	3.48	5.18	4.58

Sorting normally distributed random float32 slice (in seconds):

Library(-Mxg)	R	X	i5
sort.Slice	13.28	17.37	14.43
sortutil	1.97	3.95	3.50
zermelo	4.50	4.15	3.18
sorty-1	7.21	8.47	6.84
sorty-2	3.78	4.31	3.57
sorty-3	2.60	3.41	2.78
sorty-4	2.27	3.03	2.50
sortyLsw-1	12.77	15.65	13.40
sortyLsw-2	6.70	8.00	7.05
sortyLsw-3	4.60	6.20	5.58
sortyLsw-4	3.59	5.50	4.78

Sorting uniformly distributed random string slice (in seconds):

Library(-Mxg)	R	X	i5
sort.Slice	6.77	8.96	6.94
sortutil	1.31	2.39	1.99
radix	4.90	4.46	3.41
sorty-1	4.80	6.59	5.09
sorty-2	2.46	3.31	2.81
sorty-3	1.80	3.05	2.63
sorty-4	1.42	2.78	2.51
sortyLsw-1	6.28	8.53	6.73
sortyLsw-2	3.24	4.40	3.66
sortyLsw-3	2.20	3.74	3.29
sortyLsw-4	1.95	3.44	3.12

Sorting uniformly distributed random []byte slice (in seconds):

Library(-Mxg)	R	X	i5
sort.Slice	6.87	8.82	7.04
sorty-1	4.07	5.31	4.28
sorty-2	2.12	2.74	2.38
sorty-3	1.49	2.38	2.15
sorty-4	1.30	2.18	1.97

Sorting uniformly distributed random string slice by length (in seconds):

Library(-Mxg)	R	X	i5
sort.Slice	3.37	4.08	3.45
sorty-1	1.61	2.11	1.67
sorty-2	0.87	1.07	0.88
sorty-3	0.61	0.88	0.72
sorty-4	0.53	0.80	0.67

Sorting uniformly distributed random []byte slice by length (in seconds):

Library(-Mxg)	R	X	i5
sort.Slice	3.55	4.14	3.51
sorty-1	1.18	1.39	1.12
sorty-2	0.63	0.71	0.60
sorty-3	0.45	0.60	0.51
sorty-4	0.39	0.53	0.46

Testing & Parameter Tuning

First, make sure everything is fine:

go test -timeout 1h

You can tune Mli,Hmli,Mlr for your platform/CPU with (optimization flags):

go test -timeout 4h -gcflags '-dwarf=0 -B -wb=0' -ldflags '-s -w' -tags tuneparam

Now update Mli,Hmli,Mlr in maxc.go, uncomment imports & respective mfc*() calls in tmain_test.go and compare your tuned sorty with other libraries:

go test -timeout 1h -gcflags '-dwarf=0 -B -wb=0' -ldflags '-s -w'

Remember to build sorty (and your functions like SortObjAsc()) with the same optimization flags you used for tuning. -B flag is especially helpful.

Support

If you use sorty and like it, please support via ETH:0x464B840ee70bBe7962b90bD727Aac172Fa8B9C15

Documentation

Overview

Package sorty is a type-specific, fast, efficient, concurrent/parallel QuickSort implementation. It is in-place and does not require extra memory. You can call corresponding Sort*() to rapidly sort your slices (in ascending order) or collections of objects. For example:

sorty.SortS(string_slice) // native slice
sorty.Sort(n, lesswap)    // lesswap() function based

Index

• Constants
• Variables
• func IsSorted(n int, lsw Lesswap) int
• func IsSortedB(ar [][]byte) int
• func IsSortedF4(ar []float32) int
• func IsSortedF8(ar []float64) int
• func IsSortedI(ar []int) int
• func IsSortedI4(ar []int32) int
• func IsSortedI8(ar []int64) int
• func IsSortedLen(ar interface{}) int
• func IsSortedP(ar []uintptr) int
• func IsSortedS(ar []string) int
• func IsSortedU(ar []uint) int
• func IsSortedU4(ar []uint32) int
• func IsSortedU8(ar []uint64) int
• func Search(n int, fn func(int) bool) int
• func Sort(n int, lsw Lesswap)
• func SortB(ar [][]byte)
• func SortF4(ar []float32)
• func SortF8(ar []float64)
• func SortI(ar []int)
• func SortI4(ar []int32)
• func SortI8(ar []int64)
• func SortLen(ar interface{})
• func SortP(ar []uintptr)
• func SortS(ar []string)
• func SortU(ar []uint)
• func SortU4(ar []uint32)
• func SortU8(ar []uint64)
• type Lesswap

Constants

const (
	// Mli is the maximum slice length for insertion sort in
	// Sort*() except SortS(), SortB() and Sort().
	Mli = 100

	// Hmli is the maximum slice length for insertion sort in
	// SortS(), SortB() and Sort().
	Hmli = 40

	// Mlr is the maximum slice length for recursion when there are available
	// goroutines. So Mlr+1 is the minimum slice length for new sorting goroutines.
	Mlr = 496
)

Variables

var Mxg uint32 = 3

Mxg is the maximum concurrent goroutines (including caller) used for sorting per Sort*() call. Mxg can be changed live, even during an ongoing Sort*() call. Mxg=1 (or a short input) yields single-goroutine sorting: No goroutines or channel will be created by sorty.

Functions

func IsSorted

func IsSorted(n int, lsw Lesswap) int

IsSorted returns 0 if underlying collection of length n is sorted, otherwise it returns i > 0 with less(i,i-1) = true.

func IsSortedB

func IsSortedB(ar [][]byte) int

IsSortedB returns 0 if ar is sorted in ascending lexicographical order, otherwise it returns i > 0 with ar[i] < ar[i-1]

func IsSortedF4

func IsSortedF4(ar []float32) int

IsSortedF4 returns 0 if ar is sorted in ascending order, otherwise it returns i > 0 with ar[i] < ar[i-1]

func IsSortedF8

func IsSortedF8(ar []float64) int

IsSortedF8 returns 0 if ar is sorted in ascending order, otherwise it returns i > 0 with ar[i] < ar[i-1]

func IsSortedI

func IsSortedI(ar []int) int

IsSortedI returns 0 if ar is sorted in ascending order, otherwise it returns i > 0 with ar[i] < ar[i-1]

func IsSortedI4

func IsSortedI4(ar []int32) int

IsSortedI4 returns 0 if ar is sorted in ascending order, otherwise it returns i > 0 with ar[i] < ar[i-1]

func IsSortedI8

func IsSortedI8(ar []int64) int

IsSortedI8 returns 0 if ar is sorted in ascending order, otherwise it returns i > 0 with ar[i] < ar[i-1]

func IsSortedLen

func IsSortedLen(ar interface{}) int

IsSortedLen returns 0 if ar is sorted 'by length' in ascending order, otherwise it returns i > 0 with len(ar[i]) < len(ar[i-1]). ar's (underlying) type can be []string or [][]T (for any type T), otherwise it panics.

func IsSortedP

func IsSortedP(ar []uintptr) int

IsSortedP returns 0 if ar is sorted in ascending order, otherwise it returns i > 0 with ar[i] < ar[i-1]

func IsSortedS

func IsSortedS(ar []string) int

IsSortedS returns 0 if ar is sorted in ascending lexicographical order, otherwise it returns i > 0 with ar[i] < ar[i-1]

func IsSortedU

func IsSortedU(ar []uint) int

IsSortedU returns 0 if ar is sorted in ascending order, otherwise it returns i > 0 with ar[i] < ar[i-1]

func IsSortedU4

func IsSortedU4(ar []uint32) int

IsSortedU4 returns 0 if ar is sorted in ascending order, otherwise it returns i > 0 with ar[i] < ar[i-1]

func IsSortedU8

func IsSortedU8(ar []uint64) int

IsSortedU8 returns 0 if ar is sorted in ascending order, otherwise it returns i > 0 with ar[i] < ar[i-1]

func Search

func Search(n int, fn func(int) bool) int

Search returns lowest integer k in [0,n) where fn(k) is true, assuming:

fn(k) => fn(k+1)

If there is no such k, it returns n. It can be used to locate an element in a sorted collection.

func Sort

func Sort(n int, lsw Lesswap)

Sort concurrently sorts underlying collection of length n via lsw(). Once for each non-trivial type you want to sort in a certain way, you can implement a custom sorting routine (for a slice for example) as:

func SortObjAsc(c []Obj) {
	lsw := func(i, k, r, s int) bool {
		if c[i].Key < c[k].Key { // strict comparator like < or >
			if r != s {
				c[r], c[s] = c[s], c[r]
			}
			return true
		}
		return false
	}
	sorty.Sort(len(c), lsw)
}

Lesswap is a 'contract' between users and sorty library. Strict comparator, r!=s check, swap and returns are all strictly necessary.

func SortB

func SortB(ar [][]byte)

SortB concurrently sorts ar in ascending lexicographical order.

func SortF4

func SortF4(ar []float32)

SortF4 concurrently sorts ar in ascending order.

func SortF8

func SortF8(ar []float64)

SortF8 concurrently sorts ar in ascending order.

func SortI

func SortI(ar []int)

SortI concurrently sorts ar in ascending order.

func SortI4

func SortI4(ar []int32)

SortI4 concurrently sorts ar in ascending order.

func SortI8

func SortI8(ar []int64)

SortI8 concurrently sorts ar in ascending order.

func SortLen

func SortLen(ar interface{})

SortLen concurrently sorts ar 'by length' in ascending order. ar's (underlying) type can be []string or [][]T (for any type T), otherwise it panics.

func SortP

func SortP(ar []uintptr)

SortP concurrently sorts ar in ascending order.

func SortS

func SortS(ar []string)

SortS concurrently sorts ar in ascending lexicographical order.

func SortU

func SortU(ar []uint)

SortU concurrently sorts ar in ascending order.

func SortU4

func SortU4(ar []uint32)

SortU4 concurrently sorts ar in ascending order.

func SortU8

func SortU8(ar []uint64)

SortU8 concurrently sorts ar in ascending order.

Types

type Lesswap

type Lesswap func(i, k, r, s int) bool

Lesswap function operates on an underlying collection to be sorted as:

if less(i, k) { // strict ordering like < or >
	if r != s {
		swap(r, s)
	}
	return true
}
return false