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