# Quicksort with insertion sort

Okay so I have implemented quicksort with insertion, where K is a value until which the recursion occurs and then rest of the array is sorted using insertion sort. Now I am comaparing 3 different algorithims for sorting (quick , merge and quicKInsert). My question is is there a scenario where quickInsert out performs quick sort and merge sort running time for QuickInsert would be O(nK)+O(n log n/݇K) I have to find out a combination of N(number of elements) and K value to outperform other two sorting algos What I have tried is using k = log N did not work I know insertion sort beats quick sort in small numbers but how do I find out combination based on that. Am I missing something here

• It should possible to do an analysis of the number of comparisons. Would that suffice or do you need the actual running time? Dec 4, 2021 at 21:08
• @Michel: Comparisons and assignments. People often don't just sort integers. They might sort C++ objects (expensive to assign with a copy constructor, slightly better if you have a move constructor), or they might sort reference-counted pointers, also slightly expensive to move. Apr 8, 2022 at 11:29
• You can bind (as in upper bound) the number of assignments in terms of the number of comparisons and estimate what your actual data cost at most to move. But I assume you know that in any case. Apr 9, 2022 at 15:41

Asymptotic complexity evaluations are not appropriate to decide which implementation is the fastest, and the best you can do is to rely on empirical evaluation.

This said, there will be no absolute answer because the running time of an algorithm is not a deterministic function of the problem size. On the opposite, it is a complete statistical distribution, which is uneasy to catch.

What you can do is

• select running conditions which you think are typical in your use case(s). Usually this information is not available. You can rely on random arrays, which will give you an idea of the expected time. But better measure the standard deviation based on several runs with different data.

• working on the same arrays, try increasing values of k. Compare the times to the standard version, and conclude which is better when the averages are significantly different (say to two sigmas).

Now you can plot the relation between n and k that gives the best results.

The running time (and how it changes) of any algorithm implementation will vary across platforms (hardware, operating system, compiler etc) and the input data. So it looks hard to find a simple relation for the array size up to which insertion sort will perform better than quick sort (and that too for all inputs).

Perhaps what we can do is assume the platform factors would remain fixed and use some representative input arrays. Then test and measure time (avoiding other system noises) to find the threshold array size $$K$$ below which insertion sort becomes faster. Use this $$K$$ in the hybrid quick/insert sort to delegate to insertion sort.

Big-O is only relevant for large values. It won't help you at all trying to find the optimal K.

For Quicksort, you obviously would stop recursing for a subrange of 1 number which will be already sorted. You may very well handle subranges of length 2 differently as well like

if r ≤ l + 1
if r > l and a [l] > a [r]
exchange a[l], a[r]
return


So now you just choose K = 3, 4, 5 etc., measure the time for the combination of quick sort with insertion sort, for a range of typical arrays, and decide depending on your measurements. It is entirely possible and actually likely that for different machines the optimal K is different. If the optimal K is not trivial in size you'd also try insertion sort with binary search to find the position where to insert.