1
$\begingroup$

We have been taught that:

Insertion-sort will best work if we have a small list.

Quick-sort will best work if we have a long list.

Merge-sort will best work if we have a huge list.

It is not intuitively understandable.

However, let us say if we have a list with 20 elements and want to sort it because shifting action does cost a lot for us, that would be a perfect choice to go with Insertion-sort.

I do not know If I am getting the idea right or not, but my issue is that I can not correlate the logic behind these sorting algorithms with the size of lists, Also does worst, average and best cases affect the size list.

getting me out of confusion would be really much appreciated, thanks.

$\endgroup$
2
$\begingroup$

I'm by no means an expert, but these points are more-or-less right, however, we often use merge-sort if we suspect the array to be near (reversely) sorted.

Insertion sort is used in tiny lists (e.g. Java defines tiny to be less than 47), due to the fact that we have much less overhead in insertion sort than in merge sort and quicksort. As you may know, $O$ notation hides constants, and for two algorithms running in times $O(n^2)$ and $O(n \log n)$ respectively, the running time of the first algorithm can be smaller for small $n$.

As with quicksort, merge sort is easy to do inplace, meaning that we don't need much extra memory. However, merge sort is guaranteed to take $O(n \log n)$ whereas for subsequences of an array with a lot of structure, quicksort can take $O( n^2)$.

So, I would add one thing to your list, namely that if a list is almost reversely sorted, we prefer merge sort over quicksort.

Ps, there's a lot to learn from open source software, you can read Java's sort methods in their DualPivotQuicksort.java.

$\endgroup$
5
  • $\begingroup$ Yes, meant quicksort. But mergesort can also be done inplace. Updated. $\endgroup$ – Pål GD Mar 28 at 11:22
  • $\begingroup$ Do you have any reference to an easy in-place implementation of the merge step in mergesort? (just curious) $\endgroup$ – Steven Mar 28 at 11:22
  • $\begingroup$ I haven't checked these, but they popped up when I searched, StackOverflow Python implementation and c++ std library. $\endgroup$ – Pål GD Mar 28 at 11:42
  • 1
    $\begingroup$ Okay, so easy is in the eye of the beholder. It's easy when you're done. $\endgroup$ – Pål GD Mar 28 at 11:43
  • $\begingroup$ If I know in advance that a list is highly likely to have a tendency toward being sorted, I would use insertion sort! If I knew the would tend toward being reverse sorted, I would switch the comparison in my sort and use insertion sort (if the lists are integers, sort their negatives and multiply by -1). $\endgroup$ – awillia91 Mar 28 at 13:39
2
$\begingroup$

It's unclear to me why you put the algorithms in that order. Also, "best work" is quite informal. There are many ways to compare sorting algorithm (worst-case time, expected-time, space complexity, etc). Some considerations that might help you are below.

I can see how InsertionSort could be faster than MergeSort of QuickSort in practice for small lists.

The worst-case complexity of InsertionSort can be upper bounded by $c n^2$ for some constant $c$, while the worst-case (resp. expected) complexity of quicksort can be lower bounded by $c' n \log n$ for some $c'$. It might very well be that the multiplicative constant $c'$ is large enough to satisfy $c n^2 < c' n\log n$ for small $n$.

For huge lists, a "standard" implementation of merge sort requires $O(n)$ auxiliary space, while quick-sort can be run in place. They both have the same asymptotic expected running time, so if that's how you are comparing your algorithms, QuickSort might be preferred.

If you're comparing the algorithms by their worst case running time then it might be the case (I didn't estimate the actual constant, which depends on the specific implementation anyway) that QuickSort runs in time $\approx c_q n^2$ while MergeSort runs in time $\approx c_m n \log n$. In this case MergeSort is clearly preferred for large enough list but, if $c_q \ll c_m$, QuickSort would be preferred for moderately-sized lists.

Notice that, in practice, you can just use QuickSort (since the extra overhead spent for small lists in negligible, in the absolute sense). Fancy implementations (such as the ones often found in standard libraries) use hybrid algorithms: they run QuickSort and if they realize that the size of the subproblems is somehow not shrinking fast enough, they revert to MergeSort. Whenever the number of elements left to sort is small, they switch to a quadratic-time sorting algorithm like InsertionSort.

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