Sorting is the canonical algorithms topic. Knowing several sorts and their trade-offs is part of any working programmer's vocabulary. This chapter implements five classic algorithms in Go and explains when to use each.
Standard library
In production you almost always use the standard library:
import "sort"
sort.Ints(s) // []int
sort.Strings(s) // []string
sort.Slice(items, func(i, j int) bool { return items[i].Age < items[j].Age })
Or, since Go 1.21, the new slices package:
import "slices"
slices.Sort(s)
slices.SortFunc(items, func(a, b Item) int { return a.Age - b.Age })
sort.Sort uses introsort (pattern-defeating quicksort + heapsort fallback
+ insertion sort for small slices). It is unstable. Use sort.Stable for a
stable sort (slower).
For learning, we re-implement the classics ourselves.
Algorithms in this package
| Algorithm | Time (avg) | Time (worst) | Space | Stable | Notes |
|---|---|---|---|---|---|
| Bubble sort | O(n²) | O(n²) | O(1) | yes | Educational only. |
| Insertion sort | O(n²) | O(n²) | O(1) | yes | Excellent on small/almost-sorted data. |
| Merge sort | O(n log n) | O(n log n) | O(n) | yes | Predictable. Used for stable sort. |
| Quick sort | O(n log n) | O(n²) | O(log n) | no | Fast in practice with median-of-three. |
| Heap sort | O(n log n) | O(n log n) | O(1) | no | Worst-case bound, in place. |
The package is named sortx to avoid shadowing the standard library's
sort package.
Run the tests
go test ./part2-dsa/ds/sortx