sorty

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 than sort.Interface on generic collections.
• For each Sort*() call, sorty uses up to MaxGor concurrent goroutines (3 by default including caller) 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.
• MaxGor can be changed live, even during ongoing Sort*() calls.
• MaxLen* parameters are tuned to get the best performance, see below.
• sorty can handle NaNs with NaNoption.
• 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
• Variables
• func IsSorted(n int, lsw Lesswap) int
• func IsSortedLen(ar any) int
• func IsSortedSlice(ar any) int
• func Search(n int, fn func(int) bool) int
• func Sort(n int, lsw Lesswap)
• func SortLen(ar any)
• func SortSlice(ar any)
• type FloatOption
• type Lesswap

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

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 IsSortedLen

func IsSortedLen(ar any) 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, [][]T // for any type T

otherwise it panics.

func IsSortedSlice

func IsSortedSlice(ar any) int

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

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) 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

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 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.

func SortLen

func SortLen(ar any)

SortLen concurrently sorts ar 'by length' in ascending order. ar's (underlying) type can be

[]string, [][]T // for any type T

otherwise it panics.

func SortSlice

func SortSlice(ar any)

SortSlice concurrently sorts ar in ascending order. 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.

Types

type FloatOption

type FloatOption int32

const (
	NaNsmall FloatOption = iota - 1
	NaNignore
	NaNlarge
)

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