sorty

README

sorty

Type-specific, fast, concurrent/parallel sorting library.

sorty is an in-place QuickSort implementation (with InsertionSort as subroutine) and does not require extra memory. Call corresponding Sort*() to concurrently sort your slice (in ascending order) or collection. 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 collection concurrently. Also, 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 one channel. They are created only when necessary. Mli/Hmli/Mlr parameters are tuned to get the best performance, see below. Also, sorty uses semantic versioning.

Benchmarks

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

Machine	CPU	OS	Kernel
R	Ryzen 1600	Manjaro	5.4.74
X	Xeon Haswell	Ubuntu 20.04	5.4.0-1029-gcp
i5	Core i5 4210M	Manjaro	5.4.74

Sorting random uint32 array (in seconds):

Library(-Mxg)	R	X	i5
sort.Slice	16.03	17.94	16.10
sortutil	2.33	2.93	3.85
zermelo	2.01	1.76	1.09
sorty-2	3.32	3.76	3.21
sorty-3	2.30	2.60	2.66
sorty-4	1.77	1.95	2.30
sortyLsw-2	7.23	8.21	7.66
sortyLsw-3	4.92	5.20	6.02
sortyLsw-4	4.14	4.48	5.46

Sorting random float32 array (in seconds):

Library(-Mxg)	R	X	i5
sort.Slice	17.41	18.95	17.20
sortutil	2.90	3.15	4.47
zermelo	4.63	3.98	3.17
sorty-2	4.00	4.19	3.64
sorty-3	2.79	2.72	2.85
sorty-4	2.33	2.36	2.54
sortyLsw-2	7.95	8.59	7.97
sortyLsw-3	5.39	5.84	6.27
sortyLsw-4	4.47	4.48	5.62

Sorting random string array (in seconds):

Library(-Mxg)	R	X	i5
sort.Slice	8.34	9.48	8.44
sortutil	1.65	2.03	2.27
radix	4.29	4.40	3.50
sorty-2	2.90	3.55	3.39
sorty-3	1.99	2.48	3.07
sorty-4	1.76	1.96	2.83
sortyLsw-2	3.76	4.55	4.36
sortyLsw-3	2.57	2.94	3.99
sortyLsw-4	2.24	2.50	3.75

Testing & Parameter Tuning

First, make sure everything is fine:

go test -short -timeout 1h

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

go test -timeout 2h -gcflags '-B -wb=0 -smallframes' -ldflags '-s -w'

Now update Mli, Mlr in sorty.go and compare your tuned sorty with others:

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

Remember to build sorty (and your functions like SortObjAsc()) with the same optimization flags you used for tuning.

Support

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

Documentation

Overview

Package sorty provides type-specific concurrent / parallel sorting functionality.

sorty is an in-place QuickSort implementation and does not require extra memory. Call corresponding Sort*() to concurrently sort your slice (in ascending order) or collection. For example:

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

Index

• Variables
• func IsSorted(n int, lsw Lesswap) 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 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 SortF4(ar []float32)
• func SortF8(ar []float64)
• func SortI(ar []int)
• func SortI4(ar []int32)
• func SortI8(ar []int64)
• func SortP(ar []uintptr)
• func SortS(ar []string)
• func SortU(ar []uint)
• func SortU4(ar []uint32)
• func SortU8(ar []uint64)
• type Lesswap

Variables

var (
	// Mxg is the maximum number of goroutines used for sorting per Sort*() call.
	Mxg uint32 = 3

	// Mli is the maximum array length for insertion sort in
	// Sort*() except SortS() and Sort().
	Mli = 108
	// Hmli is the maximum array length for insertion sort in SortS() and Sort().
	Hmli = (Mli + 1) / 3

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

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 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 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 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 array or 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 { // your custom strict comparator (like < or >)
			if r != s {
				c[r], c[s] = c[s], c[r]
			}
			return true
		}
		return false
	}
	sorty.Sort(len(c), lsw)
}

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 SortP

func SortP(ar []uintptr)

SortP concurrently sorts ar in ascending order.

func SortS

func SortS(ar []string)

SortS concurrently sorts ar in ascending 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