sorting

Documentation

Index

• Constants
• func InsertionSort[T misc.Ordered](arr []T)
• func InsertionSortImmutable[T misc.Ordered](arr []T) []T
• func IsSorted[T misc.Ordered](arr []T) bool
• func MergeSort[T misc.Ordered](arr []T)
• func MergeSortIndices[T misc.Ordered](arr []T) []int
• func QuickSort[T misc.Ordered](arr []T)

Constants

const MERGE_CUTOFF = 7

Functions

func InsertionSort

func InsertionSort[T misc.Ordered](arr []T)

func InsertionSortImmutable

func InsertionSortImmutable[T misc.Ordered](arr []T) []T

func IsSorted

func IsSorted[T misc.Ordered](arr []T) bool

func MergeSort

func MergeSort[T misc.Ordered](arr []T)

sorting an array using an optimized version of mergesort (top-down)

func MergeSortIndices

func MergeSortIndices[T misc.Ordered](arr []T) []int

ret[i] is the index of the ith smallest entry in arr or: if we sort the array, ret[i] gives the original position for sorted[i]

func QuickSort

func QuickSort[T misc.Ordered](arr []T)

optimized version of quicksort (using Bentley-McIlroy 3-way partitioning, Tukey's ninther, and cutoff to insertion sort)