1
$\begingroup$

I'm trying to come up with an argument of why shell sort should be used over insertion sort for an array of 10 elements. And I'm wondering if there is one at all. I know that insertion sort is more efficient for the mostly sorted array, but in all other cases the shell sort should be faster. Or there will no significant performance difference for the array of 10 elements?

I have no knowledge about the data of an array.

$\endgroup$
  • 1
    $\begingroup$ "in all other cases the shell sort should be faster" -- what makes you say that? "no significant performance difference" -- define "significant". $\endgroup$ – Raphael May 22 '17 at 10:15
1
$\begingroup$

It's an empirical question. First you need to come up with a probability distribution on arrays, for example the uniform distribution on all permutations of $1,\ldots,n$. For each $n$, you can measure the running time of both algorithms, and see which performs faster. The threshold 10 in reality depends on the implementation and the CPU, and is quoted only because it's a "nice" number, functioning as a rule of thumb.

So far I have assumed you're interested in minimizing the average case running time. If you're interested in the worst case running time, you'll have to run the algorithms on all permutations, which will quickly become infeasible.

$\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.