0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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