Why is insertion sort faster than quick-sort and bubble-sort for small cases?

Question

I recently read an article that talked about the computation complexity of algorithms. The author mentioned "why insertion sort is faster than quick-sort and bubble-sort for small cases". Could anybody make some explanation for that?

Does anybody know the actual complexity of each sort algorithm I mentioned above?

Pullet

Did it say 'small cases' or something like 'almost-sorted cases' or 'few differences'? For small cases, a modified bubblesort is faster than insertion sort – Uncounted

@FooBah, I said small cases, which means case with small size. – Pullet

Then what you read is wrong. bubble sort is faster for small cases than insertion sort – Uncounted

@FooBah, do you have any further math support for your conclusion? I mean any math expression, or formula, please... – Pullet

Answer 1

Consider two complexity functions:

F(X) = X^2
G(X) = 4 * X * ln(X)

F(3) = 9
G(3) = 13

So algorithm F wins for 3 items. But:

F(100) = 10,000
G(100) = 1,842

So algorithm G wins for 100 items.

Insertion sort's complexity is like F(X). Quick sort's complexity is like G(X).

Pardo

The worst case complexity of naïve QuickSort is O(N^2); the normal complexity is O(N log N). The complexity of both insertion sort and bubble sort is O(N^2). – Blas

Doesn't explain how insertion sort beats bubble sort. – Uncounted

@Foo Bah: According to Sedgewick, on average Bubble sort uses N^2 / 2 comparisons and N^2 / 2 exchanges. Insertion sort uses N^2 / 4 comparisons and N^2 / 8 exchanges. Both are O(N^2), but the other factors make insertion sort faster. – Acrocarpous

@Acrocarpous I don't disagree with analysis for large N. However for small N the overhead and other effects actually support bubble sort. – Uncounted

Answer 2

If a list is already sorted, quicksort needs to go through all the recursive steps to get to n lists of size 1. Both of these take time. But the insertion sort will iterate though the list once and find out that it is done. This is the fastest for this case.

When the list is small, the overhead to make recursive calls and finding the pivot value, etc is much slower than the iterative process used in insertion sort.

Loutish

bubble sort makes 1 pass for a sorted list. You stop the sort when the list is sorted. – Uncounted

Foo Bah, good call. I was thinking about the wrong sort and have edited it – Loutish

Answer 3

Actual complexity of each sorting algorithm is as follows:

1. Best - Insertion Sort: O(N ^ 2), O(N), O(N ^ 2)
2. Average - Quick Qort: O(N ^ 2), O(N log N), O(N log N)
3. Worst - Bubble Sort: O(N ^ 2), O(N), O(N ^ 2)

Esra

Do you know the actual math expression for each of the average case? – Pullet

For Quick Sort it is T(n) = O(n) + 2T(n/2) For rest, if you have Cormen book with you, there is a thorough analysis of these algorithms. – Esra

@SITZ the rest of the world calls it CLR or CLRS – Uncounted