A channel based quicksort.

sort.go

// Channel based quicksort
//
// Just for fun!
//
// Interesting that you can make a quicksort without being able to
// index your input.  It may be O(n log n) for comparisons but it is
// O(n) for channels and go routines so perhaps not the most efficient
// quicksort ever ;-)
// 
// It also has the worst case complexity O(n²) if you feed it sorted
// input, so don't do that!
//
// Originally from: https://plus.google.com/103015172458796488244/posts/TNCvNEBdjEt
// Plaground: http://play.golang.org/p/3eR_3wCq5X

package main

import (
	"fmt"
	"math/rand"
)

// Quicksort in to out
//
// Caller must close in when finished
// Quicksort will close out when finished
func quicksort(in, out chan int) {
	defer close(out)
	pivot, ok := <-in
	// Finish recursion if no input - is sorted
	if !ok {
		return
	}
	// Divide and conquer the problem
	left_in := make(chan int)
	left_out := make(chan int)
	go quicksort(left_in, left_out)
	right_in := make(chan int)
	right_out := make(chan int)
	go quicksort(right_in, right_out)
	// Feed the two halves
	go func() {
		for i := range in {
			if i < pivot {
				left_in <- i
			} else {
				right_in <- i
			}
		}
		close(left_in)
		close(right_in)
	}()
	// Join the sorted streams
	for i := range left_out {
		out <- i
	}
	out <- pivot
	for i := range right_out {
		out <- i
	}
}

func main() {
	in := make(chan int)
	out := make(chan int)
	go quicksort(in, out)
	for i := 0; i < 100; i++ {
		in <- rand.Intn(1000)
	}
	close(in)
	for i := range out {
		fmt.Println(i)
	}
}