sorty

README

sorty

Type-specific 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(col)           // satisfies sort.Interface
sorty.Sort2(col2)         // satisfies sorty.Collection2
sorty.Sort3(n, lesswap)   // lesswap() function based

Mxg (3 by default) is the maximum number of goroutines used for sorting per Sort*() call. sorty uses semantic versioning.

'go test' results

All computers run 64-bit Manjaro Linux. Comparing against sort.Slice, sortutil, zermelo and radix with Go 1.13.5.

Sorting uint32 array (in seconds):

Library	Server with AMD Ryzen 5 1600	Desktop with Intel Core i5-2400
sort.Slice	15.99	17.37
sortutil	3.00	3.49
zermelo	2.20	1.85
sorty-2	3.20	3.08
sorty-3	2.39	2.24
sorty-4	1.98	1.81
sorty-Col	7.02	6.98
sorty-Col2	6.43	6.33
sorty-lsw	5.46	5.43

Sorting float32 array (in seconds):

Library	Server with AMD Ryzen 5 1600	Desktop with Intel Core i5-2400
sort.Slice	17.57	17.96
sortutil	3.00	4.13
zermelo	4.65	3.40
sorty-2	4.03	3.48
sorty-3	3.03	2.52
sorty-4	2.49	2.08
sorty-Col	7.81	7.27
sorty-Col2	7.06	6.52
sorty-lsw	6.27	5.63

Sorting string array (in seconds):

Library	Server with AMD Ryzen 5 1600	Desktop with Intel Core i5-2400
sort.Slice	8.54	8.03
sortutil	1.97	2.35
radix	4.63	3.31
sorty-2	3.30	3.47
sorty-3	2.53	2.56
sorty-4	2.08	2.12
sorty-Col2	3.36	3.44
sorty-lsw	3.25	3.39

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 -s' -ldflags '-s -w'

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

go test -short -timeout 1h -gcflags '-B -s' -ldflags '-s -w'

Remember to build your sorty with the same 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(col)           // satisfies sort.Interface
sorty.Sort2(col2)         // satisfies sorty.Collection2
sorty.Sort3(n, lesswap)   // lesswap() function based

Index

• Variables
• func IsSorted(ar Lesser) bool
• func IsSorted3(n int, less func(i, k int) bool) bool
• func IsSortedF4(ar []float32) bool
• func IsSortedF8(ar []float64) bool
• func IsSortedI(ar []int) bool
• func IsSortedI4(ar []int32) bool
• func IsSortedI8(ar []int64) bool
• func IsSortedP(ar []uintptr) bool
• func IsSortedS(ar []string) bool
• func IsSortedU(ar []uint) bool
• func IsSortedU4(ar []uint32) bool
• func IsSortedU8(ar []uint64) bool
• func Search(n int, fn func(int) bool) int
• func Sort(ar Collection)
• func Sort2(ar Collection2)
• func Sort3(n int, lesswap func(i, k, r, s int) bool)
• 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 Collection
• type Collection2
• type Lesser

Variables

var Mli = 96

Mli is the maximum array length for insertion sort. SortS() and Sort3() use 1/2 of this as their limits. Sort() and Sort2() use 1/4 of this as their limits.

var Mlr = 401

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.

var Mxg uint32 = 3

Mxg is the maximum number of goroutines used for sorting per Sort*() call.

Functions

func IsSorted

func IsSorted(ar Lesser) bool

IsSorted checks if ar is sorted.

func IsSorted3

func IsSorted3(n int, less func(i, k int) bool) bool

IsSorted3 checks if underlying collection of length n is sorted as per less(). An existing lesswap() can be used like:

IsSorted3(n, func(i, k int) bool { return lesswap(i, k, 0, 0) })

func IsSortedF4

func IsSortedF4(ar []float32) bool

IsSortedF4 checks if ar is sorted in ascending order.

func IsSortedF8

func IsSortedF8(ar []float64) bool

IsSortedF8 checks if ar is sorted in ascending order.

func IsSortedI

func IsSortedI(ar []int) bool

IsSortedI checks if ar is sorted in ascending order.

func IsSortedI4

func IsSortedI4(ar []int32) bool

IsSortedI4 checks if ar is sorted in ascending order.

func IsSortedI8

func IsSortedI8(ar []int64) bool

IsSortedI8 checks if ar is sorted in ascending order.

func IsSortedP

func IsSortedP(ar []uintptr) bool

IsSortedP checks if ar is sorted in ascending order.

func IsSortedS

func IsSortedS(ar []string) bool

IsSortedS checks if ar is sorted in ascending order.

func IsSortedU

func IsSortedU(ar []uint) bool

IsSortedU checks if ar is sorted in ascending order.

func IsSortedU4

func IsSortedU4(ar []uint32) bool

IsSortedU4 checks if ar is sorted in ascending order.

func IsSortedU8

func IsSortedU8(ar []uint64) bool

IsSortedU8 checks if ar is sorted in ascending order.

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(ar Collection)

Sort concurrently sorts ar.

func Sort2

func Sort2(ar Collection2)

Sort2 concurrently sorts ar.

func Sort3

func Sort3(n int, lesswap func(i, k, r, s int) bool)

Sort3 concurrently sorts underlying collection of length n via lesswap() which must be equivalent to:

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

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 { // or your custom comparator
			if r != s {
				c[r], c[s] = c[s], c[r]
			}
			return true
		}
		return false
	}
	sorty.Sort3(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 Collection

type Collection interface {
	Lesser

	// Swaps i-th and k-th elements.
	Swap(i, k int)
}

Collection is same with standard library's sort.Interface. It represents a collection of sortable (as per Less) elements.

type Collection2

type Collection2 interface {
	Lesser

	// LessSwap must be equivalent to:
	//  if less(i, k) {
	//  	swap(r, s)
	//  	return true
	//  }
	//  return false
	LessSwap(i, k, r, s int) bool
}

Collection2 is an alternative for faster interface-based sorting

type Lesser

type Lesser interface {
	// Len is the number of elements in the collection. First element has index 0.
	Len() int

	// Less (a strict ordering like < or >) reports if element-i should come
	// before element-k:
	//  Less(i,k) && Less(k,r) => Less(i,r)
	//  Less(i,k) => ! Less(k,i)
	Less(i, k int) bool
}

Lesser represents a collection of comparable elements.