Idiomatic quicksort in Go

I'm taking a look at Go, and was trying to find idiomatic implementations of classic algorithms to get a feel for the language.

I chose quicksort because I'm particularly interested in the arrays vs slices, in-place vs copy deal. After I settle some concepts down, I want to write a parallel impl.

Can someone please show me an idiomatic implementation of quicksort in Go?

Well, I ended up with this. I don't know enough Go to say it's idiomatic, but I used slices, one-line swaps and a range clause. It's been pretty informative for me to write, so I thought I should share.

func qsort(a []int) []int {
  if len(a) < 2 { return a }

  left, right := 0, len(a) - 1

  // Pick a pivot
  pivotIndex := rand.Int() % len(a)

  // Move the pivot to the right
  a[pivotIndex], a[right] = a[right], a[pivotIndex]

  // Pile elements smaller than the pivot on the left
  for i := range a {
    if a[i] < a[right] {
      a[i], a[left] = a[left], a[i]
      left++
    }
  }

  // Place the pivot after the last smaller element
  a[left], a[right] = a[right], a[left]

  // Go down the rabbit hole
  qsort(a[:left])
  qsort(a[left + 1:])


  return a
}

Take a look at the source of the sort package from the standard library, particularily sort.Sort.

Simply taking code from one language, for example C, and simplistically converting it to another language, for example Go, rarely produces idiomatic code.

> Go sort package -- sort.c source file
>
> func quickSort(data Interface, a, b, maxDepth int) {
> // . . .
> // Avoiding recursion on the larger subproblem guarantees
> // a stack depth of at most lg(b-a).
> // . . .
> }

This comment is a clue that implementing a recursive solution may not be the best strategy. Go uses short stacks.

Here's an iterative Quicksort solution.

package main
import (
"fmt"
"math/rand"
"time"
)
type Item int
type Items []Item
// Algorithms and Data Structures, N. Wirth
// http://www.ethoberon.ethz.ch/WirthPubl/AD.pdf
// 2.3.3 Partition Sort, Quicksort, NonRecursiveQuickSort.
func qSort(a Items) {
const M = 12
var i, j, l, r int
var x Item
var low, high = make([]int, 0, M), make([]int, 0, M)
low, high = append(low, 0), append(high, len(a)-1)
for { // (*take top request from stack*)
l, low = low[len(low)-1], low[:len(low)-1]
r, high = high[len(high)-1], high[:len(high)-1]
for { // (*partition a[l] ... a[r]*)
i, j = l, r
x = a[l+(r-l)/2]
for {
for ; a[i] < x; i++ {
}
for ; x < a[j]; j-- {
}
if i <= j {
a[i], a[j] = a[j], a[i]
i++
j--
}
if i > j {
break
}
}
if i < r { // (*stack request to sort right partition*)
low, high = append(low, i), append(high, r)
}
r = j // (*now l and r delimit the left partition*)
if l >= r {
break
}
}
if len(low)+len(high) == 0 {
break
}
}
}
func main() {
nItems := 4096
a := make(Items, nItems)
rand.Seed(time.Now().UnixNano())
for i := range a {
a[i] = Item(rand.Int31())
}
qSort(a)
for i := range a[1:] {
if a[i] > a[i+1] {
fmt.Println("(* sort error *)")
}
}
}

Clearly, there is more to be done. For example, improving the partitioning algorithm and changing the qsort function signature to use a Go interface type.

I'm just learning go right now and decided to implement qsort as a simple task, using channels and parallelism since in qsort you can sort both halves concurrently after pivoting the array. I ended up with smth like that:

package main
import (
"fmt"
"math/rand"
"time"
)
func qsort_pass(arr []int, done chan int) []int{
if len(arr) < 2 {
done <- len(arr)
return arr
}
pivot := arr[0]
i, j := 1, len(arr)-1
for i != j {
for arr[i] < pivot && i!=j{
i++
}
for arr[j] >= pivot && i!=j{
j--
}
if arr[i] > arr[j] {
arr[i], arr[j] = arr[j], arr[i]
}
}
if arr[j] >= pivot {
j--
}
arr[0], arr[j] = arr[j], arr[0]
done <- 1;
go qsort_pass(arr[:j], done)
go qsort_pass(arr[j+1:], done)
return arr
}
func qsort(arr []int) []int {
done := make(chan int)
defer func() {
close(done)
}()
go qsort_pass(arr[:], done)
rslt := len(arr)
for rslt > 0 {
rslt -= <-done;
}
return arr
}
func main() {
fmt.Println("About to sort.")
rand.Seed(time.Now().UTC().UnixNano())
arr_rand := make([]int, 20)
for i := range arr_rand {
arr_rand[i] = rand.Intn(10)
}
fmt.Println(arr_rand)
qsort(arr_rand)
fmt.Println(arr_rand)
}

There's plenty of room for improvement here like using a pool of go-routines instead of spawning a new go-routine for each partition, and sorting with insertion sort if len(arr) is small enough or using something other than []int. But generally it looks like a good place to start.

Could use some thoughts on this.

func quickSort(arr []int) []int {
sort(arr, 0, len(arr) - 1)
return arr
}
func sort(arr []int, low, high int) {
if low < high {
pi := partition(arr, low, high)
sort(arr, low, pi-1)
sort(arr, pi+1, high)
}
}
func partition(arr []int, low, high int) int {
pivot := arr[high]
i := low-1
for j := low; j < high; j++ {
if arr[j] <= pivot {
i++
arr[i], arr[j] = arr[j], arr[i]
}
}
arr[i+1], arr[high] = arr[high], arr[i+1]
return i+1
}

For Go 1.18 and above, using generics:

import (
"golang.org/x/exp/constraints"
)
func QuickSort[T constraints.Ordered](a []T) {
if len(a) > 1 {
quickSort(a, 0, len(a)-1)
}
}
func quickSort[T constraints.Ordered](a []T, lo, hi int) {
if lo < hi {
p := partition(a, lo, hi)
quickSort(a, lo, p-1)
quickSort(a, p+1, hi)
}
}
func partition[T constraints.Ordered](a []T, lo, hi int) int {
l, p := lo, findPivot(a, lo, hi)
for r := lo; r < hi; r++ {
if a[r] < a
 {
a[l], a[r] = a[r], a[l]
l++
}
}
a[l], a
 = a
, a[l]
return l
}
// median of three technique
func findPivot[T constraints.Ordered](a []T, lo, hi int) int {
mi := (lo + hi) / 2
if a[lo] > a[mi] {
a[lo], a[mi] = a[mi], a[lo]
}
if a[lo] > a[hi] {
a[lo], a[hi] = a[hi], a[lo]
}
if a[mi] > a[hi] {
a[mi], a[hi] = a[hi], a[mi]
}
a[mi], a[hi-1] = a[hi-1], a[mi]
return hi - 1
}

Usage:

a := []int{1, 8, 4, 9, 6, 3, 5, 2, 7, 0}
fmt.Println(a, "(original)")
QuickSort(a)
fmt.Println(a, "(sorted)")
b := []string{"tuv", "abc", "jkl", "ghi", "mno", "wxyz", "def", "pqrs"}
fmt.Println(b, "(original)")
QuickSort(b)
fmt.Println(b, "(sorted)")

func QuickSortArr(arr []int) {
var i int
var j int
var hi int
var hSave bool
aLen := len(arr)
helpArr := make([]int, aLen)
hSave = true
var tmpHelp []int
var tmpArr []int
for m := 1; m < aLen; m += m {
i = 0
j = 0 + m
hi = 0
if hSave {
tmpHelp = helpArr
tmpArr = arr
} else {
tmpHelp = arr
tmpArr = helpArr
}
for i < aLen && j < aLen {
i2 := i + m
j2 := j + m
for i < i2 && i < aLen && j < j2 && j < aLen {
if tmpArr[i] > tmpArr[j] {
tmpHelp[hi] = tmpArr[j]
hi++
j++
} else {
tmpHelp[hi] = tmpArr[i]
hi++
i++
}
}
for i < i2 && i < aLen {
tmpHelp[hi] = tmpArr[i]
hi++
i++
}
for j < j2 && j < aLen {
tmpHelp[hi] = tmpArr[j]
hi++
j++
}
i += m
j += m
}
for i < aLen {
tmpHelp[hi] = tmpArr[i]
hi++
i++
}
for j < aLen {
tmpHelp[hi] = tmpArr[j]
hi++
j++
}
hSave = !hSave
}
if !hSave {
copy(arr, helpArr)
}
}

Here's a solution I built following the Python examples in the book Grokking algorithms. It felt a little less mind bending, so I thought I'd share.

package main
import "fmt"
func main() {
list := []int{33, 10, 15, 45, 65, 16, 5}
fmt.Println(quicksort(list))
}
func quicksort(list []int) []int {
if len(list) < 2 {
return list
}
if len(list) == 2 {
left, right := 0, len(list)-1
if list[0] > list[1] {
list[left], list[right] = list[right], list[left]
}
return list
}
pivot := list[0]
var less []int
var greater []int
for i := range list {
if list[i] < pivot {
less = append(less, list[i])
}
if list[i] > pivot {
greater = append(greater, list[i])
}
}
return append(append(quicksort(less), pivot), quicksort(greater)...)
}

You can run it on the Go Playground here.