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?

  • 1
    Because computers are not identical. You are switching from a stack intensive torrent of recursive calls to a memory intensive set of loops. The latter will be most efficient if you can stay inside the size of the memory caches on the CPU. These vary from model to model, hence it is system dependent. – Thorbjørn Ravn Andersen Feb 5 '15 at 0:54
  • 1
    think of it as probably closely related to more general metrics eg the speed of the insertion sort vs speed of quicksort on $n$ items. these differences are amplified for low values of $n$ because there is less "law of averages" working out. – vzn Feb 5 '15 at 5:52
up vote 12 down vote accepted

Because the actual running time (in seconds) of real code on a real computer depends on how fast that computer runs the instructions and how fast it retrieves the relevant data from memory, how well it caches it and so on. Insertion sort and quicksort use different instructions and hava different memory access patterns. So the running time of quicksort versus insertion sort for any particular dataset on any particular system will depend both on the instructions used to implement those two sorting routines and the memory access patterns of the data. Given the different mixes of instructions, it's perfectly possible that insertion sort is faster for lists of up to ten items on one system, but only for lists up to six items on some other system.

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.

Hand-write an insertion sort and a merge sort for a list with 3 items, down to assembly code. Pay attention to:

  • # of comparisons performed
  • # of registers loaded
  • other lower level or higher level considerations: # of assembly instructions, variance introduced by the randomness in quicksort, etc.

Now see if you can give different weights to the operations that might represent two different systems - for instance, one that's comparison-optimized and one that's register loading-optimized, and compute total . If you can get different results, then it's systems-dependent. If you always get the same result, the one algorithm is always faster.

This should give you a rigorous way to think about these problems.

  • 1
    There seems to be something missing. – Raphael Feb 4 '15 at 18:54
  • Clearly, anything missing is already covered in "other computer science things". – corsiKa Feb 5 '15 at 0:00
  • 1
    Where would I find an exhaustive list of "other computer science things"? – Antonios Hadjigeorgalis May 29 '16 at 11:35
  • @AntoniosHadjigeorgalis didn't mean to imply there is one. Perhaps you're trying to save energy on a particular processor or perhaps you're performing a sort on pancakes and want to minimize the number of times the bottom of a pancake is touched. Should pancake sort go from a toy interview problem to a serious area of research you'd probably see new concepts to model this sort of question as new questions arise. The field is growing of course. – djechlin May 29 '16 at 15:50
  • Anyway I replaced the phrase that was causing offense. – djechlin May 29 '16 at 15:51

Imagine an implementation where a function call is very, very expensive. Say so expensive that in the time it takes to do one function call, you can sort an array of 1000 elements with insertion sort.

Do you think that would influence the optimal switching point?

When a partition reaches the size that can fit in a machine dependent sized cache, then it will be faster . It's more interesting to look at the mathematics behind the machine independent answer of 10 being the cut off point. C_N is the number of comparisons to sort N elements; in quick sort, each element is compared with the partitioning element until the left and right pointers cross ( so the last comparison happens once again ), so there are N + 1 comparisons for the current partitioning call. Then there are recursive calls on the left and right partitions either side of the partitioning element. In randomized quicksort, where all the elements are shuffled first, then the average number of comparisons in the two partitions is given by $ { \sum_{j=0}^N \big( C_{j-1} + C_{N-j-1} \big) \over N } $.
The goal is then to simplify the solution of the quicksort average comparison count equation , and then incorporate the given average comparison cost of insertion sort $ {j(j-1) \over 4 } $ at a given cutoff $M$. The sum is simplified, because there is symmetry of C terms around half $N$. $ {2 \over N} \sum_{j=0}^N C_{j-1} $ Eliminate the sum by subtracting the equation for $N-1$ $$ C_N = N + 1 + {2 \over N} \sum_{j=0}^N C_{j-1} $$ minus $$ C_{N-1} = (N-1) + 1 + { 2 \over N-1} \sum_{j=0}^{N-1} C_{j-1} $$ Multiply by N and N-1 respectively the equations to make the subtraction easier. $$ N C_N - (N-1) C_{N-1} = N(N+1) - (N-1)(N) + 2 \bigg(\sum_{j=0}^N C_{j-1} -\sum_{j=0}^{N-1} C_{j-1} \bigg)$$ Collecting terms and subtracting the sums, $$ N C_N = (N-1)C_{N-1} + 2N + 2 \bigg( C_{N-1} \bigg) = (N+1)C_{N-1} + 2N $$ Dividing by N(N+1) , the suitable summation factor, which simplifies to a recurrence equation that can be telescoped. $$ {C_N \over N+1} = {C_{N-1} \over N} + { 2 \over N+1} $$ Telescope, whilst maintaining that $ C_{N-1} <> C_{M} $ $$ {C_N \over N+1} = {C_{M+1} \over M+2} + \bigg(2 \sum_{j=M+3}^{N+1} {1 \over j} = 2 \big( \sum_{j=1}^{N+1} {1\over j} - \sum_{j=1}^{M+2} {1\over j} \big) \bigg) $$ $C_{M+1}$ follows the original recurrence equation, but with the insertion cost inserted instead of recursive partitioning. $$ {C_{M+1} \over M + 2} = (M+1) + 1 + 2 \sum_{j=1}^{M+1} {j(j-1) \over 4} $$ Since $ \sum_{j=1}^{P} { P \choose Q} = { P+1 \choose Q+1} $ $$ {C_{M+1} \over M + 2 } = M + 2 + 2/2 { M+2 \choose 3} = M + 2 + (M+2)(M+1)(M) / 6 $$ $$ C_{M+1} = 1 + { M(M+1) \over 6 } $$

Since $ \sum_{j=1}^N {1\over j} = H_N \approx ln N + \gamma $ , the whole equation looks like $$ C_N = (N + 1) \bigg(1+ {M(M+1) \over 6(M+2)} + 2\big(ln (N+1) - ln (M+2) \big) \bigg) $$

So for N = 1000, C_N is minimum when M = 10, independent of the machine.

This is a student answer (mine) to an Exercise from the AofA website, Introduction Analysis of Algorithms Sedgewick The answer is a middle school algebra expansion of some answers found on a discussion forum, mainly this thread : Flores, Yao and Spreng , and a it's a good idea to try to independently reach their answers. I got to the first one, and found it came up with 6 which was the wrong answer, and re-read the thread several times before being able to understand the abbreviated answer by Yao, having to dive into the book to get his assumptions , which are explained above in a middle school algebra way ( that's about my level, after 30+ years of not doing maths ).

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.