Below The Crossover

You are sorting batches. Production batches hold 20 to 60 items and always will, because the upstream API caps a page at 64. At n=48n = 48 you measure insertion sort at 1.8 microseconds and your merge sort at 6.4 microseconds. What do you do?

A

Discard the measurement. Asymptotic analysis deliberately ignores constant factors, so a 3.5x difference at a single input size carries no information.

B

Insertion sort below a measured cutoff, merge sort above it, with the cutoff and the measurement written down. This is what production sorts do: CPython's own list.sort never reaches its merge machinery below MAX_MINRUN, which is 64, and binary-insertion-sorts the whole list instead.

C

Ship merge sort. O(nlog⁡n)O(n \log n) beats O(n2)O(n^2), and that is what the notation means.

D

Ship insertion sort on its own. The batches are small, so asymptotics never enter the picture.