CODEWITHSUNDEEP
recursiongoconcurrencysynchronizationquicksort
fredoverflow
fredoverflow

Reputation: 263138

Orchestrate recursive quicksort calls via WaitGroup

I am trying to run recursive quicksort calls in parallel:

func quicksort(a []int) {
    quicksortRecursive(a)
    wg.Wait()
    insertionsort(a)
}

func quicksortRecursive(a []int) {
    if len(a) > THRESHOLD {
        l, r := partition(a)
        wg.Add(2)
        go func() {
            quicksortRecursive(a[:r+1])
            wg.Done()
        }()
        go func() {
            go quicksortRecursive(a[l:])
            wg.Done()
        }()
    }
}

The go calls appear overly clunky to me. Is the following, more readable version still correct?

func quicksort(a []int) {
    wg.Add(1)
    quicksortRecursive(a)
    wg.Wait()
    insertionsort(a)
}

func quicksortRecursive(a []int) {
    if len(a) > THRESHOLD {
        l, r := partition(a)
        wg.Add(2)
        go quicksortRecursive(a[:r+1])
        go quicksortRecursive(a[l:])
    }
    wg.Done()
}

I am specifically wondering whether calling the initial wg.Add(1) and the corresponding wg.Done() in the same thread is kosher.

Upvotes: 0

Views: 36

Answers (1)

Adrian
Adrian

Reputation: 46452

If it works correctly, then it's correct. In terms of code quality, I don't see anything wrong with the approach, other than a slight concern about the use of a global variable for the WaitGroup. If it's a small app it's probably fine, otherwise I would use a local variable created in quicksort and passed as a parameter to quicksortRecursive.

Upvotes: 2

Related Questions