parallel quicksort

gistfile1.go

package main
import (
        "fmt"
        "os"
)

type request struct {
  data []int
  replyChannel chan []int
}

func append(lesser[]int, pivot int, greater[]int) []int {
  newSlice := make([]int, (len(lesser) + len(greater) + 1))
  copy(newSlice, lesser)
  newSlice[len(lesser)] = pivot
  for i, c := range greater {
    newSlice[len(lesser) + i + 1] = c
  }
  return newSlice
}


func sort(incoming *request) {

  data := incoming.data

  if len(data) <= 1 {
    incoming.replyChannel <- data
    return
  }

  pivot, _ := pivot(data)

  lessReply, greaterReply := startListener(incoming, pivot) // create channels and listener

  less, greater := partition(data)

  // now sort the resulting sub arrays in 2 goroutines
  var lessReq, greaterReq request
  lessReq.data = less
  greaterReq.data = greater
  lessReq.replyChannel, greaterReq.replyChannel = lessReply, greaterReply

  go sort(&lessReq)

  go sort(&greaterReq)

}

func pivot(data []int) (pivot int, pivotIndex int) {
  pivotIndex = len(data)/2
  pivot = data[pivotIndex]
  return pivot, pivotIndex
}

func partition(data []int) (less []int, greater []int) {
  pivot, pivotIndex := pivot(data)
  less = make([]int, len(data))
  greater = make([]int, len(data)) //just to be on the safe side
  lessIndex := 0
  greaterIndex := 0
  for i := 0; i < len(data); i++ {
    switch {
    case i == pivotIndex:
    case data[i] <= pivot:
      less[lessIndex] = data[i]
      lessIndex += 1
    case data[i] > pivot:
      greater[greaterIndex] = data[i]
      greaterIndex += 1
    }
  }
  return less[0:lessIndex], greater[0:greaterIndex]
}

func startListener(result *request, pivot int) (lessReply chan []int, greaterReply chan []int) {
  lessReply = make(chan []int)
  greaterReply = make(chan []int)
  go sortListener(lessReply, greaterReply, result, pivot)
  return lessReply, greaterReply
}

func sortListener(lessReply chan []int, greaterReply chan []int, result *request, pivot int) {
  less, greater := false, false
  var sortedLess []int
  var sortedGreater []int
  for !(less && greater) {
    select {
      case sortedLess = <-lessReply:

        less = true
      case sortedGreater = <-greaterReply:
        greater = true
    }
  }
  appended := append(sortedLess,pivot,sortedGreater)
  result.replyChannel <- appended
}

func main() {
  data := []int{74, 59, 238, -784, 9845, 959, 905, 0, 0, 42, 7586, -5467984, 7586}

  replyChannel := make(chan []int)
  var mainRequest request
  mainRequest.data = data
  mainRequest.replyChannel = replyChannel

  sort(&mainRequest)

  result := <-replyChannel
  fmt.Fprintf(os.Stderr,"sorted %s\n", result)
}