HiveBrain v1.2.0
Get Started
← Back to all entries
snippetModerate

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
insertionwhytheoptimalcutswitchingquicksortformachinesort

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#37956, answer score: 14

Revisions (0)

No revisions yet.