Sorting

How merge sort and quicksort divide and conquer, why comparison sorting costs n log n, when counting sort beats it, and how to sort anything in Go.

Divide and conquer#

Divide the problem into smaller pieces.
Conquer each piece recursively.
Combine the answers.

Merge sort does almost all its work in step 3; quicksort does it in step 1.

Merge sort#

Split the slice in half, sort each half recursively, then merge the two sorted halves by repeatedly taking the smaller front element.

Trace [5, 2, 4, 1]:

split:      [5 2 4 1]
           /         \
       [5 2]         [4 1]
       /   \         /   \
     [5]   [2]     [4]   [1]      one element: already sorted
       \   /         \   /
       [2 5]         [1 4]        merge pairs
           \         /
           [1 2 4 5]              merge halves

The final merge step by step:

left	right	take	output
2 5	1 4	1 (right)	1
2 5	4	2 (left)	1 2
5	4	4 (right)	1 2 4
5		5 (rest of left)	1 2 4 5

Why O(n log n): halving 4 elements takes 2 levels; halving n takes log n levels. Each level merges n elements in total. So n × log n.

Merge sort is stable (equal elements keep their original order, because we take from the left on ties) and always O(n log n), but needs O(n) extra memory.

Run the trace

The recursion indents by depth, so you can see the halves split on the way down and merge on the way back up:

mergesort_trace.go

package main
 
import (
	"fmt"
	"strings"
)
 
func mergeSort(a []int, depth int) []int {
	pad := strings.Repeat("  ", depth)
	if len(a) <= 1 {
		fmt.Printf("%s%v already sorted\n", pad, a)
		return a
	}
	mid := len(a) / 2
	fmt.Printf("%ssplit %v -> %v %v\n", pad, a, a[:mid], a[mid:])
	left := mergeSort(a[:mid], depth+1)
	right := mergeSort(a[mid:], depth+1)
 
	out := make([]int, 0, len(a))
	i, j := 0, 0
	for i < len(left) && j < len(right) {
		if left[i] <= right[j] { // <= takes from the left on ties: stable
			out = append(out, left[i])
			i++
		} else {
			out = append(out, right[j])
			j++
		}
	}
	out = append(out, left[i:]...)
	out = append(out, right[j:]...)
	fmt.Printf("%smerge %v + %v -> %v\n", pad, left, right, out)
	return out
}
 
func main() {
	mergeSort([]int{5, 2, 4, 1}, 0)
}

Output

split [5 2 4 1] -> [5 2] [4 1]
  split [5 2] -> [5] [2]
    [5] already sorted
    [2] already sorted
  merge [5] + [2] -> [2 5]
  split [4 1] -> [4] [1]
    [4] already sorted
    [1] already sorted
  merge [4] + [1] -> [1 4]
merge [2 5] + [1 4] -> [1 2 4 5]

Step through it

InteractiveMerge sortSort each half recursively, then merge the two sorted halves by repeatedly taking the smaller front value.

Merge [5] and [2], both already sorted.

1 / 32

Quicksort#

Pick a pivot, partition so everything smaller is on its left and everything larger on its right, then sort both sides recursively. No merge step: after partitioning, the pivot is already in its final place.

Partition trace (Lomuto scheme) on [3, 7, 1, 6, 2] with pivot 2 (the last element); i marks where the next small element goes:

j	a[j]	`< 2`?	action	array
0	3	no		3 7 1 6 2
1	7	no		3 7 1 6 2
2	1	yes	swap a[0], a[2]; i = 1	1 7 3 6 2
3	6	no		1 7 3 6 2
end			swap pivot into a[1]	1 2 3 6 7

Quicksort sorts in place and is fast in practice, but a bad pivot (always the smallest) makes it O(n²). Choosing a random pivot makes that vanishingly unlikely. Go's slices.Sort uses pdqsort, a quicksort variant that detects bad patterns and falls back to heap sort, so it is always O(n log n).

Run the trace

partition_trace.go

package main
 
import "fmt"
 
// partition places a[hi] (the pivot) in its final position and returns that index.
func partition(a []int, lo, hi int) int {
	pivot := a[hi]
	i := lo // next slot for an element smaller than the pivot
	for j := lo; j < hi; j++ {
		if a[j] < pivot {
			a[i], a[j] = a[j], a[i]
			fmt.Printf("j=%d a[j]=%d < %d: swap into slot %d -> %v\n", j, a[i], pivot, i, a)
			i++
		} else {
			fmt.Printf("j=%d a[j]=%d >= %d: stays           -> %v\n", j, a[j], pivot, a)
		}
	}
	a[i], a[hi] = a[hi], a[i]
	fmt.Printf("pivot %d into slot %d                   -> %v\n", pivot, i, a)
	return i
}
 
func quickSort(a []int, lo, hi int) {
	if lo >= hi {
		return
	}
	p := partition(a, lo, hi)
	quickSort(a, lo, p-1)
	quickSort(a, p+1, hi)
}
 
func main() {
	a := []int{3, 7, 1, 6, 2}
	fmt.Println("first partition, pivot = last element:")
	partition(a, 0, len(a)-1)
 
	fmt.Println("full quicksort:")
	b := []int{3, 7, 1, 6, 2}
	quickSort(b, 0, len(b)-1)
	fmt.Println("sorted:", b)
}

Output

first partition, pivot = last element:
j=0 a[j]=3 >= 2: stays           -> [3 7 1 6 2]
j=1 a[j]=7 >= 2: stays           -> [3 7 1 6 2]
j=2 a[j]=1 < 2: swap into slot 0 -> [1 7 3 6 2]
j=3 a[j]=6 >= 2: stays           -> [1 7 3 6 2]
pivot 2 into slot 1                   -> [1 2 3 6 7]
full quicksort:
j=0 a[j]=3 >= 2: stays           -> [3 7 1 6 2]
j=1 a[j]=7 >= 2: stays           -> [3 7 1 6 2]
j=2 a[j]=1 < 2: swap into slot 0 -> [1 7 3 6 2]
j=3 a[j]=6 >= 2: stays           -> [1 7 3 6 2]
pivot 2 into slot 1                   -> [1 2 3 6 7]
j=2 a[j]=3 < 7: swap into slot 2 -> [1 2 3 6 7]
j=3 a[j]=6 < 7: swap into slot 3 -> [1 2 3 6 7]
pivot 7 into slot 4                   -> [1 2 3 6 7]
j=2 a[j]=3 < 6: swap into slot 2 -> [1 2 3 6 7]
pivot 6 into slot 3                   -> [1 2 3 6 7]
sorted: [1 2 3 6 7]

In the full quicksort, the first partition is the same. The left side [1] is already sorted, so the recursion moves on to the right side [3 6 7] (pivot 7, then [3 6] with pivot 6). Every element is compared only with the pivot of its current range.

Step through it

Try an already sorted input: the last-element pivot is then always the largest, and you can watch the recursion degrade to O(n²).

InteractiveQuicksort (Lomuto partition)Pick the last element as pivot, move smaller values to its left, then sort each side.

Partition indexes 0..7 around pivot 4.

1 / 29

The n log n limit, and how to beat it#

Any sort that only compares elements needs about n log n comparisons in the worst case. To go faster you must use something about the values. Counting sort works when values come from a small range: count how many of each value there are, then write them back in order. O(n + range).

Try it: counting sort

Exam scores from 0 to 10, so the range is tiny. Count first, then write each value back as many times as it was seen. No comparisons happen at all:

countingsort.go

package main
 
import "fmt"
 
func main() {
	scores := []int{7, 3, 10, 3, 7, 7, 0, 9}
	var count [11]int // one counter per possible score 0..10
	for _, s := range scores {
		count[s]++
	}
	fmt.Println("counts:", count)
 
	out := scores[:0] // reuse the same backing array
	for v, c := range count {
		for range c {
			out = append(out, v)
		}
	}
	fmt.Println("sorted:", out)
}

Output

counts: [1 0 0 2 0 0 0 3 0 1 1]
sorted: [0 3 3 7 7 7 9 10]

Sorting in Go#

Need	Use
ints, floats, strings ascending	`slices.Sort(s)`
custom order	`slices.SortFunc(s, func(a, b T) int { ... })`
keep equal elements in input order	`slices.SortStableFunc`
check if sorted	`slices.IsSorted`
older code	`sort.Ints`, `sort.Slice(s, less)`, `sort.Sort(x)`

The comparator returns negative, zero or positive. Build it with cmp.Compare, and chain keys by returning early when they differ:

slices.SortFunc(tasks, func(a, b Task) int {
	if c := cmp.Compare(b.Priority, a.Priority); c != 0 { // b first: descending
		return c
	}
	return strings.Compare(a.Name, b.Name) // then by name ascending
})

The full program#

sorting.go

package main
 
import (
	"cmp"
	"fmt"
	"math/rand"
	"slices"
	"strings"
)
 
func mergeSort(a []int) []int {
	if len(a) <= 1 {
		return a
	}
	mid := len(a) / 2
	l, r := mergeSort(a[:mid]), mergeSort(a[mid:])
	out := make([]int, 0, len(a))
	i, j := 0, 0
	for i < len(l) && j < len(r) {
		if l[i] <= r[j] { // <= keeps it stable
			out = append(out, l[i])
			i++
		} else {
			out = append(out, r[j])
			j++
		}
	}
	out = append(out, l[i:]...)
	return append(out, r[j:]...)
}
 
func quickSort(a []int) {
	if len(a) <= 1 {
		return
	}
	p := rand.Intn(len(a))
	a[p], a[len(a)-1] = a[len(a)-1], a[p] // random pivot to the end
	pivot, i := a[len(a)-1], 0
	for j := 0; j < len(a)-1; j++ {
		if a[j] < pivot {
			a[i], a[j] = a[j], a[i]
			i++
		}
	}
	a[i], a[len(a)-1] = a[len(a)-1], a[i] // pivot to its final place
	quickSort(a[:i])
	quickSort(a[i+1:])
}
 
func countingSort(a []int, maxVal int) {
	count := make([]int, maxVal+1)
	for _, v := range a {
		count[v]++
	}
	k := 0
	for v, c := range count {
		for range c {
			a[k] = v
			k++
		}
	}
}
 
type Task struct {
	Name     string
	Priority int
}
 
func main() {
	fmt.Println(mergeSort([]int{5, 2, 4, 1}))
 
	q := []int{3, 7, 1, 6, 2, 9, 2}
	quickSort(q)
	fmt.Println(q)
 
	colors := []int{2, 0, 2, 1, 1, 0}
	countingSort(colors, 2)
	fmt.Println(colors)
 
	tasks := []Task{{"deploy", 1}, {"review", 3}, {"backup", 3}, {"lunch", 2}}
	slices.SortFunc(tasks, func(a, b Task) int {
		if c := cmp.Compare(b.Priority, a.Priority); c != 0 {
			return c
		}
		return strings.Compare(a.Name, b.Name)
	})
	fmt.Println(tasks)
 
	words := []string{"go", "rust", "c", "java"}
	slices.SortStableFunc(words, func(a, b string) int { return cmp.Compare(len(a), len(b)) })
	fmt.Println(words, slices.IsSorted([]int{1, 2, 2, 5}))
}

Output

[1 2 4 5]
[1 2 2 3 6 7 9]
[0 0 1 1 2 2]
[{backup 3} {review 3} {lunch 2} {deploy 1}]
[c go rust java] true

rust and java both have 4 letters, so the stable sort kept their original order.

Complexity#

Algorithm	Best	Average	Worst	Extra space	Stable
merge sort	n log n	n log n	n log n	O(n)	yes
quicksort (random pivot)	n log n	n log n	n² (very unlikely)	O(log n) stack	no
heap sort	n log n	n log n	n log n	O(1)	no
counting sort	n + k	n + k	n + k	O(k)	yes
insertion sort	n	n²	n²	O(1)	yes
`slices.Sort` (pdqsort)	n	n log n	n log n	O(log n)	no

See the overflow bug

a - b looks like a valid comparator, but with very large or very small values the subtraction wraps around and returns the wrong sign:

comparator_bug.go

package main
 
import (
	"cmp"
	"fmt"
	"math"
	"slices"
)
 
func main() {
	nums := []int{math.MaxInt, -5, math.MinInt, 0}
 
	bad := slices.Clone(nums)
	slices.SortFunc(bad, func(a, b int) int { return a - b }) // overflows
	fmt.Println("a - b:      ", bad, slices.IsSorted(bad))
 
	good := slices.Clone(nums)
	slices.SortFunc(good, cmp.Compare[int])
	fmt.Println("cmp.Compare:", good, slices.IsSorted(good))
}

Output

a - b:       [9223372036854775807 -9223372036854775808 -5 0] false
cmp.Compare: [-9223372036854775808 -5 0 9223372036854775807] true

Summary#

Merge sort: split, sort halves, merge; stable, always O(n log n), O(n) memory.
Quicksort: partition around a pivot; in place, fast, random pivot avoids the worst case.
Comparison sorts cannot beat n log n; counting sort can when the value range is small.
In Go use slices.Sort, slices.SortFunc with cmp.Compare, and SortStableFunc when order of ties matters.

Divide and conquer#

Merge sort#

Run the trace

Step through it

Quicksort#

Run the trace

Step through it

The n log n limit, and how to beat it#

Try it: counting sort

Sorting in Go#

The full program#

Complexity#

See the overflow bug

Summary#

Check your understanding

Practice in Go