Altering my usage of channels in mergesort kills my program; OR am I misunderstanding scope when dealing with goroutines?

Issue

A few days ago, I posted this topic on the Code Review site. In it, I detailed my first attempt at implementing goroutines into my mergesort code and while it worked fine, I was hoping for a better implementation. As I thought about it more, I had what I thought was a solid idea: instead of constantly waiting for both the left and right side to complete before merging both sides together, why not take the (presumably) sorted singleton chunks you get from the left side as it is sorting itself and sorted single chunks you get from the right and sort those as they come?

I attempted to restructure my code but I’ve run into a bit of an issue: from what I can tell, my implementation of the base case has caused massive problems, or I am misunderstanding the scope of goroutines and am telling channels to close when they, in a different sort block, are still being used. I was hoping someone could help me refine my understanding or, on the chance that my code is broken in a simple fashion, help me to understand an issue I will present after this code:

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 = 2
    }
    nums = initSlice()
    ms := make(chan byte)
    go mergeSort(nums, ms)
    pos := 0
    for val := range ms {
        nums[pos] = val
        pos++
    }
    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 {
        if len(arr) == 1 { //base case
            ms <- arr[0]
        }
        close(ms)
        return
    }
    leftMS := make(chan byte)
    go mergeSort(arr[:len(arr)/2], leftMS)
    rightMS := make(chan byte)
    go mergeSort(arr[len(arr)/2:], rightMS)
    left, lOK := <-leftMS
    right, rOK := <-rightMS
    for lOK && rOK {
        leftLeast := left <= right
        if leftLeast {
            ms <- left
            left, lOK = <-leftMS
        } else {
            ms <- right
            right, lOK = <-rightMS
        }
    }
    if lOK {
        ms <- left
        for val := range leftMS {
            ms <- val
        }
    }
    if rOK {
        ms <- right
        for val := range rightMS {
            ms <- val
        }
    }
    close(ms)
}

Overall, my biggest question would be, let’s say we have the following sort:

If I am currently working through ’38’ and ’27’ pairing and I close that ms channel, I would expect it is not the same channel as the channel that starts everything off in main? If not, is there a way I can create new channels recursively while still keeping the name?

Hope this all makes sense and thanks for the help.

Solution

Your channel use is not your problem. There are two problems with your program.

First, you have to collect the results in a separate array in the main goroutine, otherwise, you’ll be modifying the array you’re sorting as it is being sorted.

Second, this block:

       } else {
            ms <- right
            right, lOK = <-rightMS

It should be

right, rOK = <-rightMS

You’re setting lOK with rightMS, not rOK.

Answered By – Burak Serdar

Answer Checked By – Jay B. (GoLangFix Admin)

Leave a Reply

Your email address will not be published.