Go: Preserve arrival order when sorting equal priorities
A priority sort can reorder jobs that share the same priority. When their arrival order should break ties, use slices.SortStableFunc and return zero for equal priorities. The stable sort keeps those jobs in their original relative order.
Set up
Tested on Linux amd64 with Go 1.26.10. Use Bash with Go on your PATH, a text editor, and the mktemp, rm, and rmdir utilities. The example uses only the standard library. Keep the same terminal through cleanup, and stop if setup fails before saving the source.
start_dir="$PWD"
work_dir="$(mktemp -d)" || exit 1
cd -- "$work_dir" || exit 1Run the example
Save as go-stable-sort-priority-ties.go:
package main
import (
"cmp"
"fmt"
"slices"
)
type Job struct {
ID string
Priority int
}
func main() {
arrivals := []Job{{"A", 2}, {"B", 1}, {"C", 2}, {"D", 1}}
queue := slices.Clone(arrivals)
slices.SortStableFunc(queue, func(a, b Job) int {
return cmp.Compare(a.Priority, b.Priority)
})
fmt.Println("sorted queue:")
for _, job := range queue {
fmt.Printf("%s priority=%d\n", job.ID, job.Priority)
}
fmt.Print("original order:")
for _, job := range arrivals {
fmt.Print(" ", job.ID)
}
fmt.Println()
if queue[0].ID != "B" || queue[1].ID != "D" || queue[2].ID != "A" || queue[3].ID != "C" {
panic("priority or tie order changed")
}
}Run:
go run go-stable-sort-priority-ties.goObserved output:
sorted queue:
B priority=1
D priority=1
A priority=2
C priority=2
original order: A B C DRead the result
Priority one comes first. Within that group, B stays before D; in priority two, A stays before C. The comparison only considers priority, so the ID has no effect on ties. Lower numbers mean earlier service in this example.
The sort changes its input slice. Cloning the arrival list first preserves the original order. These records contain only a string and an integer, so copying the elements keeps the two lists independent.
Apply it carefully
The comparator must give a consistent ordering and return zero for ties. cmp.Compare compares integers without the overflow risk of subtracting one priority from another. Do not mutate priorities while the sort runs.
Stability preserves the order supplied to the sort. If input comes from map iteration or concurrent arrivals without a defined sequence, it does not establish a reproducible tie order. Record a sequence number and compare it explicitly when that is the intended rule. slices.SortFunc does not guarantee stability, even if a small test happens to keep ties in order.
See SortStableFunc, SortFunc, and cmp.Compare.
Clean up
Remove the saved source and the empty scratch directory. Go manages its build cache separately. If the directory is not empty, inspect its contents before removing anything else.
rm -- go-stable-sort-priority-ties.go
cd -- "$start_dir" || exit 1
rmdir -- "$work_dir"
unset start_dir work_dirAcknowledgements
This post was created with assistance from AI.