sort

README

Sorting Algorithms

Merge Sort

The mere sort algorithm was inspired by this example.

pseudo code

 split each element into partitions of size 1
 recursively merge adjacent partitions
   for i = leftPartIdx to rightPartIdx
     if leftPartHeadValue <= rightPartHeadValue
       copy leftPartHeadValue
     else: copy rightPartHeadValue; Increase InvIdx
 copy elements back to original array

Documentation

Overview

Package sort is a collection of sortting algorithms

See https://visualgo.net/en/sorting for a visual example of merge sort.

Index

• func Merge(l, r []int) []int
• func MergeSort(d []int) []int

Functions

func Merge

func Merge(l, r []int) []int

Merge takes two slice of ints (assuming they are sorted) and merges them into a single slice. If the the inputs are sorted, the resulting merge will preserve the correct sorted order.

If the slices are not sorted the resulting slice will have unpredictable results.

func MergeSort

func MergeSort(d []int) []int

MergeSort takes the provided data (slice of int) and applies the merge sort algorithm, to sort the data. The runtime of merge sort is at best, at worst, and at average always O(n * logn).