Recursive Mergesort using goroutines

Question

When learning a new language, one of my first tasks I like to go through is writing a few different sorting algorithms in that language to help familiarize myself with the syntax and see if there are creative ways that algorithm can be conceived in the language.

In Go, I wanted to use this as an opportunity to work with Goroutines and see if there are other interesting functions/uses that I had missed while writing this out. Effectively, my goal is to have the divide-and-conquer portion of the algorithm happen concurrently.

One possible area of improvement would be to have the combination of the left and right sides also happen concurrently, rather than wait for the left and right sides to complete before moving on to combining. Overall, my concerns boil down to:

1) How could I, if possible, use concurrency inside/around the for loops from the mergesort function to speed up the end portion of the algorithm?

2) Other than the algorithm itself which, to my understanding, already is in the "sort" package, are there any other Go-specific problems with my code that could be made more..."Go-thic"?

package main

import (
    "crypto/rand"
    "fmt"
    "os"
    "strconv"
)

var (
    nums    []byte //The slice of numbers we want to sort
    numVals int    = -1
)

//User can optionally add a parameter that determines how many random numbers will be sorted
//If none are provided, 100 will be used
func main() {
    if len(os.Args) >= 2 {
        numVals, _ = strconv.Atoi(os.Args[1])
    } else {
        numVals = 100
    }
    nums = initSlice()
    ms := make(chan []byte)
    go mergeSort(nums, ms)
    nums = <-ms
    for _, value := range nums {
        fmt.Printf("%d\n", value)
    }
}

func initSlice() []byte {
     vals := make([]byte, numVals)
     _, err := rand.Read(vals)
     if err != nil {
        panic(err)
     }
     return vals
}

func mergeSort(arr []byte, ms chan []byte) {
    if len(arr) <= 1 { //base case
        ms <- arr
        return
    }
    leftMS := make(chan []byte)
    go mergeSort(arr[:len(arr)/2], leftMS)
    rightMS := make(chan []byte)
    go mergeSort(arr[len(arr)/2:], rightMS)
    left, right := <-leftMS, <-rightMS
    sortArr := make([]byte, len(arr))
    lIndex, rIndex := 0, 0
    //Combine both sides
    for lIndex < len(left) && rIndex < len(right) {
        leftLeast := left[lIndex] <= right[rIndex]
        if leftLeast {
            sortArr[lIndex+rIndex] = left[lIndex]
            lIndex++
        } else {
            sortArr[lIndex+rIndex] = right[rIndex]
            rIndex++
        }
    }
    //Fill in whichever 'pile' is empty
    if lIndex < len(left) {
        for ; lIndex < len(left); lIndex++ {
            sortArr[lIndex+rIndex] = left[lIndex]
        }
    }
    if rIndex < len(right) {
        for ; rIndex < len(right); rIndex++ {
            sortArr[lIndex+rIndex] = right[rIndex]
        }
    }
    ms <- sortArr
}

Of course, please feel free to add any other suggestions. Thanks!

Answer 1

1. Keep your global environment clean - no need to define nums and numVals globally. Just create them in the main function and pass them to the appropriate functions.

   nums := initSlice(size)
   

2. You can save on memory by creating the sortArr array at the initialization phase, and pass it along with arr.

   go mergeSort(arr[:len(arr)/2], res[:len(sortArr)/2], leftMS)
   go mergeSort(arr[len(arr)/2:], res[len(sortArr)/2:], rightMS)
   

3. You can init numVals to 100 and then change it if an arg was provided:

   size := 100
   if len(os.Args) >= 2 {
       size, _ = strconv.Atoi(os.Args[1])
   }
   

4. Add a buffer to leftMS and rightMS. This way their goroutines will be closed when they are done. Currently if the right side is done before the left, then it will have to wait because you are reading leftMS first.

   leftMS, rightMS := make(chan []byte, 1), make(chan []byte, 1)
   

5. Comments always start with an empty space: //Combine both sides -> // Combine both sides

Answer 2

1. I don't think there is actually a need for two channel. Whether the sub-slice is from the left part or the right part does not matter when you merge, you can simply use a single channel.

   MS := make(chan []byte)
   go mergeSort(arr[:len(arr)/2], MS)
   go mergeSort(arr[len(arr)/2:], MS)
   left, right := <-MS, <-MS
   

   This is better because it avoids potential blocking when right is completed before left.

2. Repitively calculating lIndex+rIndex is verbose. Use a variable to record index of sortArr. And use var statement to declare variables that does not need initial value. Go's if statement allows a short statement before the condition; use it to simplify variables:

   var index, lIndex, rIndex int
   //Combindexne both sides
   for lIndex < len(left) && rIndex < len(right) {
       if l, r := left[lIndex], right[rIndex]; l <= r {
           sortArr[index] = l
           lIndex++
       } else {
           sortArr[index] = r
           rIndex++
       }
       index++
   }
   

3. To fill the remaining sortArr, Go has a copy builtin. Since only one slice is not empty, it is safe to copy without advancing index.

   copy(sortArr[index:], left[lIndex:])
   copy(sortArr[index:], right[rIndex:])