The last step showed what an unstable sort does to eight items. Here is what it did to a working system.

How transit builds its timetable graph

At every stop, transit sorts all the departure events by time and links them into a chain: you stand at the stop, time passes, you move from one departure to the next.

The detail that matters: a node only reaches its chain SUCCESSORS. From an event you can get to later ones, never earlier — time runs one way.

The chain is sorted with sort.Slice. And sort.Slice is unstable.

What happened

The Vilnius timetable is recorded to the minute, so tied departure times are common — several buses leave in the same second.

transit solves the same route on two graphs: the full service day, and a narrower time window. Both use the same sort on the same data.

The unstable sort put the tied events in a different order in the two graphs. And because a node only reaches its successors, that meant the two graphs disagreed about which vehicles a traveller could catch at all.

transit's own source records it like this:

"Ties on departure MUST break deterministically. With an unstable sort, a stop whose events share a departure time gets a different chain order in the windowed and full-day graphs, and since a node only reaches its chain SUCCESSORS, the two graphs then disagree about which vehicles are catchable. That produced real mismatches until this tiebreak was added."

The fix

sort.Slice(chain, func(a, b int) bool {
    ea, eb := t.Events[chain[a]], t.Events[chain[b]]
    if ea.Departure != eb.Departure {
        return ea.Departure < eb.Departure
    }
    return chain[a] < chain[b]   // ← ties decided by index
})

The second line is the whole repair. When departure times are equal, the original index decides. The sort stays unstable, but the comparison becomes total: there is no longer any pair whose relative order is undefined.

You can make an unstable sort deterministic by adding a key that never ties. Merge sort does not need one — that single <= gives it determinism for free.

What to take from it

This was not a speed bug and not a crash. The program ran, returned routes, and never reported a problem. It was simply that two versions of the same computation disagreed, and that disagreement was the only signal anything was wrong.

Those are the expensive bugs: silent, irregular, and dependent on data that usually does not occur — until your city starts running two buses in the same second.