sort.Interface and Custom Orders

## The interface Go's `sort` package sorts anything that can answer three questions about itself: ```go type Interface interface { Len() int Less(i, j int) bool Swap(i, j int) } ``` - **`Len() int`** — how many elements there are. The sort calls this exactly once, at the start, to learn `n`; it then works only with indices in `[0, n)`. - **`Less(i, j int) bool`** — reports whether the element at index `i` **must sort before** the element at index `j`. Note the wording: it is a *strict* "before", not "before or equal". If `Less(i, j)` and `Less(j, i)` are both false, the sort treats the two elements as equal. - **`Swap(i, j int)`** — exchanges the elements at the two indices, in place. ## Why indices and not values This interface predates generics, and its shape is the reason `sort` works on any container at all, not just slices: a linked structure, a pair of parallel slices, a struct wrapping a slice plus a cached key — anything that can count, compare by position and swap by position. The sort algorithm never touches an element value and never allocates a copy of your data. That is also why `Swap` exists: the package cannot move elements it cannot see, so your type has to move them for it. ## The idiom The conventional implementation is a **named slice type** carrying the three methods: ```go type Row struct { Region string Score int } type byScore []Row func (r byScore) Len() int { return len(r) } func (r byScore) Less(i, j int) bool { return r[i].Score < r[j].Score } func (r byScore) Swap(i, j int) { r[i], r[j] = r[j], r[i] } ``` and then `sort.Sort(byScore(rows))`. The conversion `byScore(rows)` is free — it does not copy the elements, only reinterprets the slice's type. A **value receiver** is correct here and often surprises newcomers. `Swap` mutates the caller's data even though `r` is a copy, because copying a slice copies its three-word header (pointer, length, capacity) and the pointer still aims at the same backing array. If instead you implement the interface on a **struct** that holds the slice, a value receiver is still fine for the same reason; you only need a pointer receiver if a method must change the length or replace the slice itself. ## Who consumes the interface Once a type satisfies `sort.Interface` it can be handed to several functions: - `sort.Sort(data)` — orders it, with no guarantee about the relative order of elements your `Less` treats as equal. - `sort.Stable(data)` — orders it while keeping equal elements in their original relative order. - `sort.IsSorted(data)` — reports whether it is already ordered according to your `Less`. - `sort.Reverse(data)` — returns another `sort.Interface` with the ordering flipped. The package also ships adapters for the trivial element types: `sort.IntSlice`, `sort.StringSlice` and `sort.Float64Slice` are named slice types that already implement the three methods, so `sort.Sort(sort.IntSlice(nums))` needs no code of your own. ## The contract your Less must honour `Less` is expected to describe a consistent ordering. The package documents two transitivity requirements: if `Less(i, j)` and `Less(j, k)` are both true then `Less(i, k)` must be true, and if `Less(i, j)` and `Less(j, k)` are both false then `Less(i, k)` must be false too. A common way to break the second rule is writing `<=` instead of `<`, which claims that two equal elements each sort before the other. It also means `Less` must not consult anything that changes during the sort — reading a package-level variable that another goroutine mutates, or comparing against an element captured by value before elements started moving, produces an ordering the sort cannot make sense of. ## What it costs Sorting through this interface is allocation-free and in place, but every comparison and every move is an **interface method call**, which the compiler generally cannot inline. For a hot path over a large batch that is the main cost of the approach; for the overwhelming majority of code it is irrelevant and the readability of a named type with a named ordering wins.