Why is the optimal cut-off for switching from Quicksort to Insertion sort machine dependent?

Problem Detail: 

I fail to understand why cut off value would be system dependent, and not a constant.

From Princeton University website

Cutoff to insertion sort. As with mergesort, it pays to switch to insertion sort for tiny arrays. The optimum value of the cutoff is system-dependent, but any value between 5 and 15 is likely to work well in most situations.

Would it be safe to assume that optimal cut off value is equal to optimal set size for Insert sort?

Asked By : Matas Vaitkevicius

Answered By : supercat

The relative costs of various operations are different on different machines, and compilers have varying degrees of ability to optimize various constructs. David Richerby goes into somewhat more detail on that, but the last half-sentence of the highlighted quote is perhaps the most important. In many cases where one algorithm is more efficient than another for small data sets, and another is more efficient for large data sets, the performance differences between the two algorithms are apt to be rather small for data sets near the "break-even" point. As a simple example, assume for numerical simplicity that the cost of insertion sort is precisely $C_1 · N·N$ with some constant $C_1$, and the cost of quick sort is precisely $C_2 · N·\lg(N)$ for some other constant $C_2$. Then consider the relative behaviors for two sets of constants.

First of all, suppose that the constants are $C_1 =1$ and $C_2 = 2$. Then for $N=4$ both sorts will take time 16; for $N=16$, insertion sort will take time 256 and quick sort will take time 128. For $N=8$, insertion sort will take time 64 and quick sort will take time 48.

Now suppose the constants are $C_1 = 1$ and $C_2 = 4$. Then for $N=4$, insertion sort will take time 16 while quick sort will take time 32; for $N=16$, both sorts will take time 256. For $N=8$, insertion sort will take time 64 and quick sort will take time 96.

In the former scenario, the break-even point was 4, and in the latter it was 16, but despite the $4:1$ difference in break-even point, the time required for insertion sort and quick sort will be within 50% of each other for $N=8$. If one knows that the real situation is somewhere between those two scenarios, determining the exact break-even point may allow some performance improvement versus simply using a value of 8, but using 8 will be at most 50% worse than using the optimal value. Note further that because a program is unlikely to spend most of its time sorting regions of size 8, the 50% difference in time to sort regions of that size will generally have only a small effect on overall sorting performance.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/37956