implement algorithms on golang

kormen_sorts.go

package main

import "fmt"

func merge(left []int, right []int) []int {
	var result []int
	for len(left) != 0 && len(right) != 0 {
		if left[0] < right[0] {
			result = append(result, left[0])
			left = left[1:]
		} else {
			result = append(result, right[0])
			right = right[1:]
		}
	}

	return append(result, append(left, right...)...)
}

func mergeSort(ary []int) []int {
	if len(ary) == 1 {
		return ary
	}

	q := len(ary) / 2
	left := mergeSort(ary[:q])
	right := mergeSort(ary[q:])
	return merge(left, right)
}

func selectionSort(ary []int) []int {
	for i := 1; i < len(ary); i++ {
		for j := 0; j < i; j++ {
			if ary[i] < ary[j] {
				ary[i], ary[j] = ary[j], ary[i]
			}
		}
	}
	return ary
}

func insertionSort(ary []int) []int {
	for i := 1; i < len(ary); i++ {
		key := ary[i]
		j := i - 1
		for j >= 0 && ary[j] > key {
			ary[j+1] = ary[j]
			j--
		}
		ary[j+1] = key
	}
	return ary
}

func partition(ary []int, p int, r int) int {
	q := p
	for u := p; u < r; u++ {
		if ary[u] <= ary[r] {
			ary[q], ary[u] = ary[u], ary[q]
			q += 1
		}
	}
	ary[q], ary[r] = ary[r], ary[q]
	return q
}

func _quickSort(ary []int, p int, r int) {
	if r < p {
		return
	}

	q := partition(ary, p, r)
	_quickSort(ary, p, q-1)
	_quickSort(ary, q+1, r)
	return
}

func quickSort(ary []int) []int {
	_quickSort(ary, 0, len(ary)-1)
	return ary
}

func main() {
	a := []int{3, 2, 1, 4, 5, -1}
	fmt.Println("input data: ", a)
	fmt.Println("merge sort\t", mergeSort(a))
	fmt.Println("quick sort\t", quickSort([]int{3, 2, 1, 4, 5, -1}))
	fmt.Println("selection sort\t", selectionSort([]int{3, 2, 1, 4, 5, -1}))
	fmt.Println("insertion sort\t", insertionSort([]int{3, 2, 1, 4, 5, -1}))
}

sort.go

package main

import "fmt"

// Сортировка вставками
func InsertionSort(ary []int) []int {
	for i := 1; i < len(ary); i++ {
		x := ary[i]
		j := i

		for j > 0 && x < ary[j-1] {
			ary[j] = ary[j-1]
			j -= 1
		}
		ary[j] = x
	}
	return ary
}

// Бинарная сортировка вставками
func BinaryInsertionSort(ary []int) []int {
	for i := 0; i < len(ary); i++ {
		x := ary[i]
		l, r := 0, i

		for l < r {
			m := (l + r) / 2
			if ary[m] <= x {
				l = m + 1
			} else {
				r = m
			}
		}
		for j := i; j > r; j-- {
			ary[j] = ary[j-1]
		}
		ary[r] = x
	}
	return ary
}

// Сортировка простым выбором
func StraightSelection(ary []int) []int {
	for i := 0; i < len(ary)-1; i++ {
		currentIndex := i
		currentValue := ary[i]

		for j := i + 1; j < len(ary); j++ {
			if ary[j] < currentValue {
				currentIndex = j
				currentValue = ary[j]
			}
		}
		ary[currentIndex] = ary[i]
		ary[i] = currentValue
	}
	return ary
}

// пузырьковая сортировка
func BubbleSort(ary []int) []int {
	for i := 1; i < len(ary); i++ {
		for j := len(ary) - 1; j >= i; j-- {
			if ary[j-1] > ary[j] {
				x := ary[j-1]
				ary[j-1] = ary[j]
				ary[j] = x
			}
		}
	}
	return ary
}

func main() {
	fmt.Println([]int{5, 4, 3, 2, 5, 4, 3, 2, 1})
	fmt.Println("InsertionSort", InsertionSort([]int{5, 4, 3, 2, 5, 4, 3, 2, 1}))
	fmt.Println("BinaryInsertionSort", BinaryInsertionSort([]int{5, 4, 3, 2, 5, 4, 3, 2, 1}))
	fmt.Println("StraightSelection", StraightSelection([]int{5, 4, 3, 2, 5, 4, 3, 2, 1}))
	fmt.Println("BubbleSort", BubbleSort([]int{5, 4, 3, 2, 5, 4, 3, 2, 1}))
}