A good example in this direction is N-body force calculations (or here). An $O(N^2)$ algorithm performs better compare to $O(NlogN)$ ones up to a break-even point even 50K particles. This is a good paper explaining this;
Pringle, Gavin J. "Comparison of an O (N) and an O (N log N) N-body solver."