README
¶
Sort
This package contains implementations of Radix Sort, Quicksort, Merge Sort and Insertion Sort in Go.
In addition, it provides the functions InsertSorted and MergeSortedSets.
All implementations use generics and can operate on ordered primitive types as defined by cmp.Ordered.
Sorting is performed in-place where possible and the input slice is always updated. As a convenience, it is returned as well.
Benchmarks for all supported functions can be found in benchmark.md.
Radix Sort
Radix Sort is a sorting algorithm that can operate in linear time O(n) for certain inputs.
This implementation currently only supports integer types (signed and unsigned), falling back to slices.Sort automatically for all other types of data.
Since Radix Sort is very difficult to implement efficiently in-place, this implementation creates a copy of the data.
Sorting is performed using 256 buckets which means a single byte of the input items is processed at a time.
sort.RadixSort[T cmp.Ordered](items []T) []T
The implementation is based on the design by Austin G. Walters described in Radix Sort in Go (Golang)
Quicksort
Quicksort is a very versatile and fast sorting algorithm.
A more optimized version is part of the standard library as slices.Sort and should be used instead of this implementation.
In-place sorting means that no additional memory is allocated.
While the average complexity is O(n log n), Quicksort has a worst-case complexity of O(n²).
The standard library implementation gets around this by falling back to Heap Sort in certain cases.
sort.QuickSort[T cmp.Ordered](items []T) []T
This implementation is based on the Hoare partition scheme and has been adapted from the pseudocode on Wikipedia Quicksort
Merge Sort
Merge Sort is a sorting algorithm that works by recursively merging sorted slices, starting from a size of 1.
It is a stable sorting algorithm meaning items with the same value will retain their original order.
The worst-case complexity is O(n log n), but it generally performs slightly worse than a well-optimized Quicksort.
An in-place implementation is not possible, meaning a copy of the items is created in the process.
sort.MergeSort[T cmp.Ordered](items []T) []T
A part of merge sort, the function MergeSortedSets is exposed as well.
It efficiently combines two already sorted sets.
This can be useful for combining the results of distributed (or multithreaded) sorting algorithms as well as inserting multiple elements (which can quickly be sorted e.g. using insertion sort) into a large, already sorted slice.
sort.MergeSortedSets[T cmp.Ordered](a []T, b []T) []T
Insertion Sort
Insertion Sort is a very simply but inefficient sorting algorithm that works by starting with a single value and then adding one item after the other at the right position to keep the result sorted.
It operates in-place and can be very efficient for small sets since it does not depend on recursion, but with a complexity of O(n²), it does not scale well.
sort.InsertionSort[T cmp.Ordered](items []T) []T
The insertion process of Insertion Sort can be used individually to efficiently insert a single element into an already sorted slice.
sort.InsertSorted[T cmp.Ordered](sorted []T, insert T) []T
Documentation
¶
Index ¶
- func InsertSorted[T cmp.Ordered](sorted []T, insert T) []T
- func InsertionSort[T cmp.Ordered](items []T) []T
- func MergeSort[T cmp.Ordered](items []T) []T
- func MergeSortedSets[T cmp.Ordered](a, b []T) []T
- func QuickSort[T cmp.Ordered](items []T) []Tdeprecated
- func RadixSort[T cmp.Ordered](items []T) []T
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func InsertSorted ¶
InsertSorted inserts a single element into an already sorted slice. It is more efficient at this operation than resorting the entire array.
func InsertionSort ¶
InsertionSort implements insertion sort for all ordered primitive types. It is only good for very small slices or almost sorted data. For larger, unsorted values its complexity is O(n²), leading to very poor performance.
func MergeSort ¶
MergeSort implements merge sort for all ordered primitive types. It is a stable sorting algorithm, therefore maintaining the order of elements that have the same value. The implementation does not operate in-place, temporarily allocating a copy of the data that needs to be sorted. The worst-case performance is O(n log n) with a static space requirement of O(2n)
func MergeSortedSets ¶
MergeSortedSets merges two already sorted slices very efficiently. It is used as part of merge sort but can also be useful when inserting multiple elements into a sorted slice (though the elements to insert first have to be sorted) or when combining the results of distributed sorting algoritms.
func QuickSort
deprecated
func RadixSort ¶
RadixSort implements radix sort using byte-by-byte sorting with 256 buckets for all integer types. It creates an internal copy of the supplied data, leading to one large allocation. The result is updated in-place and returned for convenience as well. Other data types such as float64, float32 and string are handled via a fallback to slices.Sort. Signed integers are handled by flipping the sign bit before and after sorting and treating them as unsigned integers. The computational complexity is O(n) with a space requirement of O(2n).
Types ¶
This section is empty.
Source Files