README
¶
sorts is a package for playing around with various sorts in Go.
All the sorts so far conform to Go's sort.Interface, which poses some interesting challenges -- pertty much everything has to be in place, which makes things interesting.
Documentation
¶
Overview ¶
sorts is a playground for experimenting with various stable sort algorithms. All these conform to the usual Go sort interface. For now, there is just a basic insertion sort, the stable sort from the standard library, and an implementation of powersort.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func InsertionSort ¶
InsertionSort is a simple insertion sort. It is very cache-friendly for small amounts of data, but the runtime costs are terrible for more than 32 or so items
func Powersort ¶
powersort, an adaptive mergesort, described here: https://arxiv.org/pdf/1805.04154.pdf The key improvement powersort makes over the standard library merge sort is in carefully choosing when to merge adjacent runs of already sorted data based on their calculated position in a nearly-optimal binary merge tree. It really needs a lower level merge function that deals well with unequal merge lengths. Its behaviour does not appear to play nicely with symmerge from the standard libary.
Source Files