3 ms·
But this optimisation is applied many times: it is the leaf case of such qsort algorithms. So it affects the constant scaling factor at all ns, not just for sm
by chalst 16y ago
But this optimisation is applied many times: it is the leaf case of such qsort algorithms. So it affects the constant scaling factor at all ns, not just for small ns.
- JoachimSchipper 16y agoI thought I was being totally clear, but seeing your comment and its upvotes, apparently not. What exactly did your "but" refer to? I think we're in complete agreement... (I was trying to say: here's an example where properly using a fast-for-few-elements "toy" algorithm can improve real-world performance on a "serious" problem like sorting a big chunk of data. So big-O is not everything.)
- chalst 16y agoThe point is that this improvement doesn't deliver a speed up that is significant only for small n, but a speed up everywhere. I agree that fast on small n does matter, it's just that this isn't an example.
- JoachimSchipper 16y agoThanks for clarifying! (Still, you get a global speedup because the "inner" algorithm is fast for small n.)