Skip to main content
Code Review

Return to Answer

deleted 46 characters in body
Source Link
peterSO
peterSO
  • 3.6k
  • 14
  • 14
$ go test msort.go msort_test.go -bench=. -benchmem
BenchmarkMergeSortBenchmarkMSort-4   18720    64849 ns/op    98048 B/op    999 allocs/op

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

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

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

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

$ go test msort.go msort_test.go -bench=. -benchmem
BenchmarkMSort-4   6996  150493 ns/op  242880 B/op  3996 allocs/op
added 1782 characters in body
Source Link
peterSO
peterSO
  • 3.6k
  • 14
  • 14

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
BenchmarkMergeSort-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
BenchmarkMergeSort-4    6996   150493 ns/op   242880 B/op   3996 allocs/op

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
BenchmarkMergeSort-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
BenchmarkMergeSort-4    6996   150493 ns/op   242880 B/op   3996 allocs/op
Source Link
peterSO
peterSO
  • 3.6k
  • 14
  • 14

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