sort

README

sort

Sort	Best Case	Average Case	Worst Case	Memory	Comment
InsertionSort	N2 / 2	N2 / 2	N2 / 2	1	N exchanges, Suitable for small N
ShellSort	N	?	?	1	Tight code, Subquadratic
MergeSort	NlgN	NlgN	NlgN	N	Stable, NlgN guarantee, Extra memory
MergeSortRec	NlgN	NlgN	NlgN	N	Stable, NlgN guarantee, Extra memory
HeapSort	NlgN	NlgN	NlgN	1	NlgN guarantee
QuickSort	NlgN	2NlnN	N2 / 2	clogN	NlgN probabilistic guarantee
QuickSort3Way	N	2NlnN	N2 / 2	clogN	Faster in presence of duplicate keys

By running benchmarks, you can compare the performance of these algorithms with each other and also with built-in sort algorithm of go.

Documentation

Index

• func HeapSort(a []interface{}, compare func(a, b interface{}) int)
• func InsertionSort(a []interface{}, compare func(a, b interface{}) int)
• func MergeSort(a []interface{}, compare func(a, b interface{}) int)
• func MergeSortRec(a []interface{}, compare func(a, b interface{}) int)
• func QuickSort(a []interface{}, compare func(a, b interface{}) int)
• func QuickSort3Way(a []interface{}, compare func(a, b interface{}) int)
• func Select(a []interface{}, k int, compare func(a, b interface{}) int) interface{}
• func ShellSort(a []interface{}, compare func(a, b interface{}) int)
• func Shuffle(a []interface{})

Functions

func HeapSort

func HeapSort(a []interface{}, compare func(a, b interface{}) int)

HeapSort implements heap sort algorithm

func InsertionSort

func InsertionSort(a []interface{}, compare func(a, b interface{}) int)

InsertionSort implements insertion sort algorithm

func MergeSort

func MergeSort(a []interface{}, compare func(a, b interface{}) int)

MergeSort implements merge sort algorithm in an iterative manner

func MergeSortRec

func MergeSortRec(a []interface{}, compare func(a, b interface{}) int)

MergeSortRec implements merge sort algorithm in a recursive manner

func QuickSort

func QuickSort(a []interface{}, compare func(a, b interface{}) int)

QuickSort implements quick sort algorithm

func QuickSort3Way

func QuickSort3Way(a []interface{}, compare func(a, b interface{}) int)

QuickSort3Way implements 3-way quick sort algorithm

func Select

func Select(a []interface{}, k int, compare func(a, b interface{}) int) interface{}

Select finds the kth smallest item of an array in O(n) time on average

func ShellSort

func ShellSort(a []interface{}, compare func(a, b interface{}) int)

ShellSort implements shell sort algorithm

func Shuffle

func Shuffle(a []interface{})

Shuffle shuffles an array in O(n) time