Implementing Quick Sort in Go

Welcome Gophers! In this lesson, we are going to implement the Quick Sort algorithm in Go. In the last lesson, we covered how the algorithm works conceptually — now let’s put it into practice.

Setting Up

Let’s create a new file called main.go in a directory called 02-quick-sort/:

package main

import "fmt"

func main() {
  fmt.Println("Quick Sort Algorithm in Go")
}

The QuickSort Function

Let’s start with our function signature. We want it to take a slice of ints and sort it in place:

func QuickSort(array []int) []int {
  // base case — arrays of 0 or 1 elements are already sorted
  if len(array) < 2 {
    return array
  }
}

Now here’s where the magic happens. We need to:

Pick a pivot (we’ll use the last element)
Partition the array around that pivot
Recursively sort each partition

func QuickSort(array []int) []int {
  if len(array) < 2 {
    return array
  }

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

  // choose the last element as our pivot
  pivot := right

  // partition: move everything smaller than pivot to the left
  for i := range array {
    if array[i] < array[pivot] {
      array[i], array[left] = array[left], array[i]
      left++
    }
  }

  // put the pivot in its final position
  array[left], array[right] = array[right], array[left]

  // recursively sort each partition
  QuickSort(array[:left])
  QuickSort(array[left+1:])

  return array
}

Let’s walk through what’s happening here. We iterate through every element and compare it to our pivot. If it’s smaller, we swap it to the left side and bump our left pointer. Once we’re done, the pivot goes into position at left — everything before it is smaller, everything after is larger.

Then we just call QuickSort again on the two halves. The recursion handles the rest.

Testing It Out

Let’s wire it up in our main function:

func main() {
  fmt.Println("Quick Sort Algorithm in Go")

  unsorted := []int{5, 3, 8, 1, 2, 4}
  fmt.Println("Before:", unsorted)

  sorted := QuickSort(unsorted)
  fmt.Println("After: ", sorted)
}

Run it:

$ go run main.go
Quick Sort Algorithm in Go
Before: [5 3 8 1 2 4]
After:  [1 2 3 4 5 8]

Brilliant — our array is sorted!

Writing Proper Tests

Let’s add a test file main_test.go to make sure it works across different cases:

package main

import (
  "reflect"
  "testing"
)

func TestQuickSort(t *testing.T) {
  tests := []struct {
    name     string
    input    []int
    expected []int
  }{
    {"basic", []int{5, 3, 4, 1, 2}, []int{1, 2, 3, 4, 5}},
    {"already sorted", []int{1, 2, 3, 4, 5}, []int{1, 2, 3, 4, 5}},
    {"reverse sorted", []int{5, 4, 3, 2, 1}, []int{1, 2, 3, 4, 5}},
    {"single element", []int{42}, []int{42}},
    {"empty", []int{}, []int{}},
    {"duplicates", []int{3, 1, 3, 2, 1}, []int{1, 1, 2, 3, 3}},
  }

  for _, tt := range tests {
    t.Run(tt.name, func(t *testing.T) {
      result := QuickSort(tt.input)
      if !reflect.DeepEqual(result, tt.expected) {
        t.Errorf("got %v, want %v", result, tt.expected)
      }
    })
  }
}

$ go test -v
=== RUN   TestQuickSort
=== RUN   TestQuickSort/basic
=== RUN   TestQuickSort/already_sorted
=== RUN   TestQuickSort/reverse_sorted
=== RUN   TestQuickSort/single_element
=== RUN   TestQuickSort/empty
=== RUN   TestQuickSort/duplicates
--- PASS: TestQuickSort (0.00s)
PASS

All passing — nice.

Conclusion

We now have a solid Quick Sort implementation in Go. The key takeaway is the partition step — once you understand how elements get shuffled around the pivot, the recursion takes care of the rest.

In the next lesson, we’ll look at the Bubble Sort algorithm, which takes a completely different approach.