Is an O(n log n) algorithm always better than O(n squared) here

Only past the crossover point. With constants \(c_1\) and \(c_2\), the comparison is \(c_1 n \log n\) against \(c_2 n^2\), so the quadratic version wins while \(n < c_1 \log n / c_2\). For small n with a cache-friendly layout that boundary is often in the thousands, which is why insertion sort survives inside real sort implementations.

The orders of magnitude, not the digits:

The useful consequence: one network call costs as much as a million memory accesses, so batching calls beats optimising the code between them.

Classic signature of a cache that misses under load: every miss now pays the lookup plus the original work, and the population step often serialises on a lock. Measure hit rate before and after, and add jitter to expiry so entries do not all die in the same second.

When you stop noticing it. If it has not surfaced a problem in six months, it is either solved or it was never the bottleneck you thought.