Implementation of merge sort and bubble sort

Question

I'm new to Go and looking for a review of my merge sort and bubble sort implementations. What can be done better? Can my code be cleaner/clearer?

// algos.go
// (C) 2014 splashinn
// Implement two types of sorting algorithms; merge sort and bubble sort

package main

import (
    "fmt"
    "time"
    "math/rand"
)

func main() {

    var n int
    fmt.Printf("How long of an array should we sort? (≤1000) ")
    _, err := fmt.Scanf("%d", &n)
    if err != nil {
        fmt.Println("Error:", err)
        return
    }
    if n > 1000 {
        fmt.Println("Error:", n, "> 1000 - too long!")
        return
    } else if n < 1 {
        fmt.Println("Error:", n, "< 1")
        return
    }

    array := make([]int, n)
    rand.Seed(time.Now().UTC().UnixNano())

    fmt.Println("Original Array:")
    for i := range array {
        array[i] = rand.Intn(10000)
        fmt.Printf("%d\t", array[i])
    }
    fmt.Println()

    bubbleSortedArray := BubbleSort(array)

    fmt.Println("Bubble Sorted Array: ")
    for i := range bubbleSortedArray {
        fmt.Printf("%d\t", bubbleSortedArray[i])
    }
    fmt.Println()

    mergeSortedArray := MergeSort(array)

    fmt.Println("Merge Sorted Array: ")
    for i := range mergeSortedArray {
        fmt.Printf("%d\t", mergeSortedArray[i])
    }
    fmt.Println()
}

// Implementing bubble sort
func BubbleSort(inputArray []int) (sortedArray []int) {
    array := make([]int, len(inputArray))
    copy(array, inputArray)
    for i := 0; i < len(array)-1; i++ {
        for j := 0; j < len(array)-1; j++ {
            if array[j] > array[j+1] {
                // Idiomatic Go swap
                array[j], array[j+1] = array[j+1], array[j]
            }
        }
    }
    return array
}

// Implementing a top-down merge sort
// Adapted from the Merge Sort C code from Wikipedia
func MergeSort(array []int) (sortedArray []int) {
    sortedArray = make([]int, len(array), cap(array))
    splitMerge(array, sortedArray)
    return array
}

func splitMerge(A []int, B []int) {
    if(len(A) < 2) {   // if run size == 1, consider it sorted
        return
    }
    // recursively split runs into two halves until run size == 1,
    // then merge them and return back up the call chain
    iMiddle := len(A) / 2              // iMiddle = mid point
    splitMerge(A[:iMiddle], B[:iMiddle])  // split / merge left  half
    splitMerge(A[iMiddle:], B[iMiddle:])  // split / merge right half
    merge(A, B, iMiddle)  // merge the two half runs
    copy(A, B)             // copy the merged runs back to A
}

func merge(A []int, B []int, iMiddle int) {
    i0 := 0
    i1 := len(A) / 2
    iEnd := len(A)

    for j := range A {
        // If left run head exists and is <= existing right run head.
        if (i0 < iMiddle && (i1 >= iEnd || A[i0] <= A[i1])) {
            B[j] = A[i0]
            i0++  // Increment i0 after using it as an index.
        } else {
            B[j] = A[i1]
            i1++  // Increment i1 after using it as an index.
        }
    }
}

Answer 1

I don't see any major problems but there are a number of (really very minor) little nits.

First, the trend seems to be for people to like very few blank lines. I think this trend is driven by the prevalence of syntax highlighting. I recently I had the occasion to program on a machine without syntax highlighting and found that I wanted more blank lines again for readability. Anecdotes aside though, try using fewer blank lines and see if you like it after you get used to it.

In your first if statement, you could use the "simple statement" form

if _, err := fmt.Scanf("%d", &n); err != nil {
    fmt.Println("Error:", err)
    return
}

Most Go programmers like that this form more clearly associates the if statement with the code that is being tested and that the scope of err here is limited to the if body. It also saves a line of screen real estate.

Consider replacing sequences of if statements with a single switch statement.

switch _, err := fmt.Scanf("%d", &n); {
case err != nil:
    fmt.Println("Error:", err)
    return
case n > 1000:
    fmt.Println("Error:", n, "> 1000 - too long!")
    return
case n < 1:
    fmt.Println("Error:", n, "< 1")
    return
}

The usual arguments for preferring switch over a chain of ifs are that the logic is easier to follow and the code is more readable. As with the simple statement form of if, this form also restricts variable scope and tends to need few lines on the screen.

array := make([]int, n) presents some issues.

The word "array" has a general meaning in computing, but has a specific meaning in Go. Some Go programmers are bothered when Go slices are incorrectly called arrays. It's disturbing in the way something like var integer float64 would be. You might still argue that array is appropriate here because it identifies the conceptual thing you have obtained from the user and retains the language of the user interface. Or in the interest of code readability, you might consider other names, or consider different terminology in the user interface.

In BubbleSort, you can replace

array := make([]int, len(inputArray))
copy(array, inputArray)

with

array := append([]int{}, inputArray...)

if you like. The first form is easy to understand and is arguably more readable. The second form is a little tricky but is listed on Slice Tricks on the Go Wiki and I think is pretty common.

It looks like your for loops in BubbleSort could use the range clause form.

And then you have some if statements with unnecessary parentheses. Otherwise looks great.

Answer 2

Not Go-specific since I've only skimmed the syntax, but good advice in any language, you should refactor main to extract several methods:

• readInteger(description, min, max) to prompt for, read, and validate the size of the array. This will simplify the logic since you can return a value or an error and drop all those returns.

• Create a random array.

• Output an array.

• If Go supports function pointers or closures, apply a list of sort methods to an array and output the result of each. Or better, validate that the result of each is correctly sorted.