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");
}