Go Mergesort

gistfile1.go

func merge(arr []int, start, mid, end int) {
  var sorted = make([]int, (end - start) + 1)
	sortPos := 0
	leftPos := start
	rightPos := mid + 1

	for ;sortPos < len(sorted); {
		if !(leftPos > mid || rightPos > end) {
			if arr[leftPos] < arr[rightPos] {
				sorted[sortPos] = arr[leftPos]
				sortPos = sortPos + 1
				leftPos = leftPos + 1
			} else {
				sorted[sortPos] = arr[rightPos]
				sortPos = sortPos + 1
				rightPos = rightPos + 1
			}
		 } else {
			if leftPos <= mid {
				sorted[sortPos] = arr[leftPos]
				sortPos = sortPos + 1
				leftPos = leftPos + 1
			} else if rightPos <= end {
				sorted[sortPos] = arr[rightPos]
				sortPos = sortPos + 1
				rightPos = rightPos + 1
			} else {
				break
			}
		 }
	}

	for i := 0; i < len(sorted); i++ {
		arr[i] = sorted[i]
	}
}

func mergeSort(arr []int, start, end int) {
	if start < end {
		mid := (end + start) / 2
		mergeSort(arr, start, mid)
		mergeSort(arr, mid + 1, end)
		merge(arr, start, mid, end)
	}
}