并发快速排序

Question

So I've implemented a quicksort algorithm in go. I tested it with go test, works perfectly well. Now I wanted to make it concurrent and check the differences in computational times. Algorithm looks like this:

package mysort

import (
    "math/rand"
)

// ConcurrentPartition - ConcurrentQuicksort function for partitioning the array (randomized choice of a pivot)
func ConcurrentPartition(A []int, p int, r int) int {
    index := rand.Intn(r-p) + p
    pivot := A[index]
    A[index] = A[r]
    A[r] = pivot
    x := A[r]
    j := p - 1
    i := p
    for i < r {
        if A[i] <= x {
            j++
            tmp := A[j]
            A[j] = A[i]
            A[i] = tmp
        }
        i++
    }
    temp := A[j+1]
    A[j+1] = A[r]
    A[r] = temp
    return j + 1
}

// ConcurrentQuicksort - a concurrent version of a quicksort algorithm
func ConcurrentQuicksort(A []int, p int, r int) {
    if p < r {
        q := ConcurrentPartition(A, p, r)
        ConcurrentQuicksort(A, p, q-1)
        ConcurrentQuicksort(A, q+1, r)
    }
}

Every ConcurrentQuicksort is actuall independent by default as its build on divide and conquer philosophy. So the only thing I did was adding go keyword before every recursive call, like this:

go ConcurrentQuicksort(A, p, q-1)
go ConcurrentQuicksort(A, q+1, r)

I didnt't work. As I've seen it just took a array and didn't even once called the recursive quicksort. So I've added time import and this line:

time.Sleep(time.Second * 2) (thats after if)

And it worked. So I guess it needed time to complete all the operations. How can I now make it without waiting? Should I use channel, or maybe call the functions differently?

@Edit Added this:

func ConcurrentQuicksort(A []int, p int, r int, wg *sync.WaitGroup) {
    if p < r {
        q := ConcurrentPartition(A, p, r)
        wg.Add(2)
        go ConcurrentQuicksort(A, p, q-1, wg)
        go ConcurrentQuicksort(A, q+1, r, wg)
    }
}

Answer 1

You could use the sync package here. Creating a WaitGroup will actually do not go further down the thread until all of your go routines are actually done. It has pretty trivial interface. Here is the example of usage.

func main() {
    var wg sync.WaitGroup

    for i := 0; i < 1000; i++ {
        wg.Add(1)
        go func(index int) {
            defer wg.Done()
            fmt.Println("I'm done and my index is", index)
        }(i)
    }

    wg.Wait()

    fmt.Println("This message is actually printed after all goroutines are done")
}