I'm reading "Introduction to Algorithms" by CLRS and I can't find an implementation of the pseudo code from the book in golang. By the original implementation I mean that we deal with extra parameters in the function to define slice of an original array. All implementations on the web deal with whole array. And that's not what Thomas Cormen wanted. So I write this one:
package sort_merge
import (
"math"
)
/*
CLRS implementation - we deal with slice of original array arr[p, r], indexes p and r are inclusive
*/
// arr={6, 5, 4, 3}; p=0; q=3
// arr={6, 5}; p=0; q=1
// arr={6}; p=0; q=0
func MergeSort(arr []int, p int, r int) {
if p < r {
q := (p + r) / 2 // last index of left array (rounding down)
MergeSort(arr, p, q)
MergeSort(arr, q+1, r)
Merge(arr, p, q, r)
}
}
func Merge(arr []int, p int, q int, r int) {
left := make([]int, len(arr[p:q+1])) // q+1, because right part of slice is exclusive
right := make([]int, len(arr[q+1:r+1])) // q+1, because this is last index of left array
copy(left, arr[p:q+1])
copy(right, arr[q+1:r+1]) // r+1, because right part of slice is exclusive
left = append(left, math.MaxInt64) // math.MaxInt64 used here as Infinity from original implementation
right = append(right, math.MaxInt64)
i, j := 0, 0
for k := p; k <= r; k++ {
if left[i] <= right[j] {
arr[k] = left[i]
i++
} else { // left[i] > right[j]
arr[k] = right[j]
j++
}
}
}
You can run it:
package main
import "fmt"
import "./sort-merge"
func main() {
arr := []int{6, 5, 4, 3}
sort_merge.MergeSort(arr, 0, len(arr)-1)
fmt.Println(arr)
}