shlomil

//Filename: mtquicksort.go  - By Shlomil 2009 - public domain
package main

import "fmt"

func partition(arr [] int, pivot int) int
{
    if len(arr)==0 {
        return pivot;
    }
    pivotval := arr[pivot];
    arr[pivot] , arr[0] = arr[0] , arr[pivot];
    var store = len(arr)-1;
    for i:=len(arr)-1; i>=1; i-- {
        if arr[i] >= pivotval {
            arr[i] , arr[store] =  arr[store] , arr[i];
            store--;
        }
    }
    arr[store] , arr[0] =  arr[0] , arr[store];
    return store;
}

func quicksort(arr [] int, done chan bool) {
    if len(arr) < 2 {
        done <- true;
        return;
    }
    var done_left = make(chan bool);
    var done_right = make(chan bool);
    pivot := partition(arr, len(arr)/2);
    go quicksort(arr[0:pivot],done_left);
    go quicksort(arr[pivot+1:len(arr)],done_right);
    done <- ((<-done_left) && (<-done_right));
    return;
}

func parallel_quicksort(arr [] int) {
    var d = make(chan bool);
    go quicksort(arr,d);
    <-d;
}

func main()
{
    var a = [7]int{1,5,3,8,2,2,0};

    parallel_quicksort(&a);

    for _,v := range a {
        fmt.Printf("%d,",v);
    }
    fmt.Printf("\n");
}