jfcg / Sorty

sorty

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

sorty is a concurrent QuickSort implementation (with InsertionSort as subroutine). 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

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 is stable, 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.15.7 on:

Sorting random uint32 array (in seconds):

Sorting random float32 array (in seconds):

Sorting random string array (in seconds):

Testing & Parameter Tuning

First, make sure everything is fine:

go test -short -timeout 1h

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

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

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

go test -short -timeout 1h -gcflags '-B -wb=0' -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