Go中并行Quicksort的死锁

As an exercise I'm trying to implement a parallel version of quicksort in Go. This is what I have so far:

func quicksort(nums []int, ch chan int, level int, threads int)  {
  level *= 2;
  if len(nums) == 1 {  ch<- nums[0]; close(ch); return }

  less := make([]int, 0)
  greater := make([]int,0)
  pivot := nums[0]
  nums = nums[1:]

  for _,i := range nums{
    switch{
    case i <= pivot:
      less = append(less,i)
    case i > pivot:
      greater = append(greater,i)
    }
  }

  ch1 := make(chan int, len(less))
  ch2 := make(chan int, len(greater))
  if(level <= threads){
    go quicksort(less, ch1, level, threads)
    go quicksort(greater,ch2, level, threads)
  }else{
    quicksort(less,ch1, level, threads)
    quicksort(greater,ch2, level, threads)
  }

  for i := range ch1{
    ch<-i;
  }
  ch<-pivot
  for i := range ch2{
    ch<-i;
  }
  close(ch)
  return
}

However, when I run it, I get an error claiming the program has deadlocked! I'm pretty stumped to what is causing this...

Thanks in advance,

Linus

The code has one problem, and at least one potential buggy usage case:

1. It is missing a base case. Consider what happens if quicksort is asked to sort the empty slice.
2. When calling quicksort for the first time, say in a main(), if you don't spawn the sorter in a separate goroutine, the main thread, running the toplevel sort, can block trying to write back to the channel (depending if the toplevel channel itself is buffered).

For example:

func main() {
    x := []int{3, 1, 4, 1, 5, 9, 2, 6}
    ch := make(chan int)
    quicksort(x, ch, 0, 0)    // buggy!
    for v := range(ch) {
        fmt.Println(v)
    }
}

This is buggy because this asks the main thread to do the sort, but it will inevitably block at this part of quicksort: it can't communicate with itself!

for i := range ch1{
    ch<-i;
}

and it's at the write to the toplevel channel here that the main thread will deadlock.

Contrast this with what happens if we do create a goroutine at toplevel:

func main() {
    x := []int{3, 1, 4, 1, 5, 9, 2, 6}
    ch := make(chan int)
    go quicksort(x, ch, 0, 0)
    for v := range(ch) {
        fmt.Println(v)
    }
}

and now we avoid that particular deadlock problem.