CLRS implementation (opportunity to sort subarray) of merge sort in golang

Question

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)
}

Answer 1

I'm reading "Introduction to Algorithms" by CLRS and I can't find an implementation of the pseudo code from the book in golang.

---

Here is my Go implementation of the pseudocode from the book.

package main
import (
 "fmt"
 "math"
)
// Introduction to Algorithms
// Third Edition
// Cormen, Leiserson, Rivest, Stein
func merge(a []float64, p, q, r int) {
 nLeft := q - p + 1
 nRight := r - q
 t := make([]float64, (nLeft+1)+(nRight+1))
 left := t[:nLeft+1]
 right := t[nLeft+1:]
 copy(left[:nLeft], a[p:])
 copy(right[:nRight], a[q+1:])
 left[nLeft] = math.Inf(0)
 right[nRight] = math.Inf(0)
 i, j := 0, 0
 for k := p; k <= r; k++ {
 if left[i] <= right[j] {
 a[k] = left[i]
 i++
 } else {
 a[k] = right[j]
 j++
 }
 }
}
// MergeSort sorts the slice a[p:r+1] in nondecreasing order.
func MergeSort(a []float64, p, r int) {
 if p < r {
 q := (p + r) / 2
 MergeSort(a, p, q)
 MergeSort(a, q+1, r)
 merge(a, p, q, r)
 }
}
func main() {
 a := []float64{9: 2, 4, 5, 7, 1, 2, 3, 6}
 fmt.Println(a)
 MergeSort(a, 9, 16)
 fmt.Println(a)
}

---

---

This is a real-world code review: Code should be correct, maintainable, robust, reasonably efficient, and, most importantly, readable.

Your code is not readable. Your code does not closely follow the pseudocode. For example, you deleted the n1 and n2 pseudocode variables:

n1 = q - p + 1
n2 = r - q

As a result, your code is very inefficient. Your code is off-by-one.

The Go Programming Language Specification

Appending to and copying slices

The variadic function append appends zero or more values x to s of type S, which must be a slice type, and returns the resulting slice, also of type S. ... If the capacity of s is not large enough to fit the additional values, append allocates a new, sufficiently large underlying array that fits both the existing slice elements and the additional values. Otherwise, append re-uses the underlying array.

For left and right subarrays, you allocate slice with a capacity equal to the number of elements, then you immediately append a sentinel value. This allocates a new slice and copies the old values from the old slice to the new slice.

In my code, I renamed n1 and n2 to a more readable nLeft and nRight. In my code, I minimized the number and size of allocations.

A benchmark (1000 random elements) for my code

$ go test msort.go msort_test.go -bench=. -benchmem
BenchmarkMSort-4 18720 64849 ns/op 98048 B/op 999 allocs/op

versus a benchmark (1000 random elements) for your code

$ go test msort.go msort_test.go -bench=. -benchmem
BenchmarkMSort-4 6996 150493 ns/op 242880 B/op 3996 allocs/op

• maxim-glyzin: Thanks for the review, I rewrite my solution with n1 and n2. I understand inefficient parts of my code, but what is "not readable" in it?