>  Toward that end it would be fine to use "very high" cutoffs, and save tuning for later.

This feels reasonable to me -- I changed the cutoff to the more cautious `if (m >= 100 && n - m >= 5000)`, where the averages are very consistently faster by my measurements, and it seems that Tal confirms that, at least for the `m >= 100` part. More tuning may be worth exploring later, but this seems pretty safe for now, and it should fix all of the truly catastrophic cases like in the original post.