sorter

Documentation

Index

• Constants
• type MSBRadixInterface
• type Sorter
  • func NewMsbRadixSorter(maxLength int, sorter MSBRadixInterface) Sorter
  • func NewPdqSorter(data sort.Interface) Sorter

Constants

const (
	// LEVEL_THRESHOLD
	// after that many levels of recursion we fall back to introsort anyway
	// this is used as a protection against the fact that radix sort performs
	// worse when there are long common prefixes (probably because of cache
	// locality)
	LEVEL_THRESHOLD = 8

	// HISTOGRAM_SIZE
	// size of histograms: 256 + 1 to indicate that the string is finished
	HISTOGRAM_SIZE = 257

	// LENGTH_THRESHOLD
	// buckets below this size will be sorted with introsort
	LENGTH_THRESHOLD = 100
)

const (
	// INSERTION_SORT_THRESHOLD
	// Below this size threshold, the sub-range is sorted using Insertion sort.
	INSERTION_SORT_THRESHOLD = 16
)

const (
	// SINGLE_MEDIAN_THRESHOLD
	// Below this size threshold, the partition selection is simplified to a single median.
	SINGLE_MEDIAN_THRESHOLD = 40
)

Types

type MSBRadixInterface

type MSBRadixInterface interface {
	Compare(i, j, skipBytes int) int
	Swap(i, j int)
	ByteAt(i int, k int) int
}

type Sorter

type Sorter interface {
	Sort(from, to int)
}

func NewMsbRadixSorter

func NewMsbRadixSorter(maxLength int, sorter MSBRadixInterface) Sorter

func NewPdqSorter

func NewPdqSorter(data sort.Interface) Sorter