README
¶
sorty 
sorty is a type-specific, fast, efficient, concurrent / parallel sorting library. It is an innovative QuickSort implementation, hence in-place and does not require extra memory. You can call:
import "github.com/jfcg/sorty/v2"
sorty.SortSlice(native_slice) // []int, []float64, []string etc. in ascending order
sorty.SortLen(len_slice) // []string or [][]T 'by length' in ascending order
sorty.Sort(n, lesswap) // lesswap() 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 any type equivalent to
[]int, []int32, []int64, []uint, []uint32, []uint64,
[]uintptr, []float32, []float64, []string, [][]byte,
[]unsafe.Pointer, []*T // for any type T
sorty also natively sorts any type equivalent to []string or [][]T (for any type T)
by length.
sorty is stable (as in version), well-tested and pretty careful with resources & performance:
lesswap()operates faster thansort.Interfaceon generic collections.- For each
Sort*()call, sorty uses up toMaxGor(3 by default, including caller) concurrent goroutines and up to one channel. - Goroutines and channel are created/used only when necessary.
MaxGor=1(or a short input) yields single-goroutine sorting: no goroutines or channel will be created.MaxGorcan be changed live, even during an ongoingSort*()call.MaxLen*parameters are tuned to get the best performance, see below.- sorty API adheres to semantic versioning.
sorty does not yet recognize partially sorted (sub-)slices to sort them faster (like pdqsort).
Benchmarks
See Green tick > QA / Tests > Details. Testing and benchmarks are done with random inputs
via jfcg/rng library.
Testing & Parameter Tuning
Run tests with:
go test -timeout 1h -v
You can tune MaxLen* for your platform/CPU with:
go test -timeout 3h -tags tuneparam
Now you can update MaxLen* in maxc.go and run tests again to see the improvements.
The parameters are already set to give good performance over different CPUs.
Also see Green tick > QA / Tuning > Details.
Support
See Contributing, Security and Support guides. Also if you use sorty and like it, please support via Github Sponsors or:
- BTC:
bc1qr8m7n0w3xes6ckmau02s47a23e84umujej822e - ETH:
0x3a844321042D8f7c5BB2f7AB17e20273CA6277f6
Documentation
¶
Overview ¶
Package sorty is a type-specific, fast, efficient, concurrent / parallel sorting library. It is an innovative QuickSort implementation, hence in-place and does not require extra memory. You can call:
import "github.com/jfcg/sorty/v2" sorty.SortSlice(native_slice) // []int, []float64, []string, []*T etc. in ascending order sorty.SortLen(len_slice) // []string or [][]T 'by length' in ascending order sorty.Sort(n, lesswap) // lesswap() based
Index ¶
Constants ¶
const MaxLenIns = 60
MaxLenIns is the default maximum slice length for insertion sort.
const MaxLenInsFC = 30
MaxLenInsFC is the maximum slice length for insertion sort when sorting strings or calling Sort().
const MaxLenRec = 600
MaxLenRec is the default maximum slice length for recursion when there is goroutine quota. So MaxLenRec+1 is the minimum slice length for new sorting goroutines.
const MaxLenRecFC = 300
MaxLenRecFC is the maximum slice length for recursion when sorting strings or calling Sort().
Variables ¶
var MaxGor uint64 = 3
MaxGor is the maximum number of goroutines (including caller) that can be concurrently used for sorting per Sort*() call. MaxGor can be changed live, even during ongoing Sort*() calls. MaxGor ≤ 1 (or a short input) yields single-goroutine sorting: sorty will not create any goroutines or channel.
var NaNoption = NaNlarge
NaNoption determines how sorty handles NaNs in SortSlice() and IsSortedSlice(). NaNs can be treated as smaller than, ignored or larger than other float values. By default NaNs will end up at the end of your ascending-sorted slice. If your slice contains NaNs and you choose to ignore them, the result is undefined behavior, and almost always not sorted properly. sorty is only tested with small/large options.
Functions ¶
func IsSorted ¶
IsSorted returns 0 if underlying collection of length n is sorted, otherwise it returns i > 0 with less(i,i-1) = true.
func IsSortedLen ¶
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, [][]T // for any type T
otherwise it panics.
func IsSortedSlice ¶
IsSortedSlice returns 0 if ar is sorted in ascending order, otherwise it returns i > 0 with ar[i] < ar[i-1]. ar's (underlying) type can be
[]int, []int32, []int64, []uint, []uint32, []uint64, []uintptr, []float32, []float64, []string, [][]byte, []unsafe.Pointer, []*T // for any type T
otherwise it panics.
func Search ¶
Search returns lowest integer k in [0,n) where fn(k) is true, assuming:
fn(k) implies 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 ¶
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 SortTypeAscending(slc []Type) {
lsw := func(i, k, r, s int) bool {
if slc[i].Key < slc[k].Key { // strict comparator like < or >
if r != s {
slc[r], slc[s] = slc[s], slc[r]
}
return true
}
return false
}
sorty.Sort(len(slc), lsw)
}
Lesswap is a contract between users and sorty. Strict comparator, r!=s check, swap and returns are all necessary.
Types ¶
type FloatOption ¶ added in v2.1.0
type FloatOption int32
const ( NaNsmall FloatOption = iota - 1 NaNignore NaNlarge )
Source Files