mege sort for golang

merge_sort.go

package main

import "fmt"

func main() {
	length := 1000
	slice := make([]int, length)
	for i := 0; i < length; i++ {
		slice[i] = i
	}

	rand.Shuffle(length, func(i, j int) {
		slice[i], slice[j] = slice[j], slice[i]
	})

	MergeSort(slice)

	for i := 0; i < length-1; i++ {
		cur := slice[i]
		next := slice[i+1]
		if next < cur {
			panic("not sort")
		}
	}
}

// MergeSort is merge sort function
func MergeSort(src []int) {
	mergeSort(src, 0, len(src)-1)
}

func mergeSort(slice []int, l, r int) {
	if l >= r {
		return
	}

	mid := (l + r) / 2
	mergeSort(slice, l, mid)
	mergeSort(slice, mid+1, r)
	merge(slice, l, mid, r)
}

func merge(slice []int, l, mid, r int) {
	aux := make([]int, r-l+1)
	copy(aux, slice[l:r+1])

	leftIndex := l
	rightIndex := mid + 1
	for index := l; index <= r; index++ {
		if leftIndex > mid {
			slice[index] = aux[rightIndex-l]
			rightIndex++
		} else if rightIndex > r {
			slice[index] = aux[leftIndex-l]
			leftIndex++
		} else if leftValue, rightValue := aux[leftIndex-l], aux[rightIndex-l]; leftValue < rightValue {
			slice[index] = leftValue
			leftIndex++
		} else {
			slice[index] = rightValue
			rightIndex++
		}
	}
}