Merge sort uses Divide and Conquer to split inputs and merge the halfs so they are sorted.
Given some numbers sort via merge sort:
[1,3,2]
[1] , [3, 2]
[1] , [3] , [2]
[1,2], [3]
[1,2,3]
Can someone help me with adding in the GinkGo Tests?
package main
import "fmt"
func merge_sort(slice []int) []int {
length := len(slice)
if length < 2 {
return slice
}
mid := (length) / 2
return merge(merge_sort(slice[:mid]), merge_sort(slice[mid:]))
}
func merge(left, right []int) []int {
size, l, r := len(left)+len(right), 0, 0
slice := make([]int, size, size)
for i := 0; i < size; i++ {
if l > len(left)-1 && r <= len(right)-1 {
slice[i] = right[r]
r++
} else if r > len(right)-1 && l <= len(left)-1 {
slice[i] = left[l]
l++
} else if left[l] < right[r] {
slice[i] = left[l]
l++
} else {
slice[i] = right[r]
r++
}
}
return slice
}
func main() {
arr := []int{3, 4, 1, 2, 5}
fmt.Print(merge_sort(arr))
}