Why is insertion sorting faster than quicksort sorting and bubble sorting for small cases?

Question

I recently read an article that talked about the complexity of computing algorithms. The author mentioned "why insertion sorting is faster than quicksort sorting and bubble sorting for small cases." Can anyone explain this?

Does anyone know the real complexity of each sorting algorithm mentioned above?

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 3 items. But:

F (100) = 10000
G (100) = 1,842

Thus, algorithm G wins 100 units.

The complexity of sorting an insert is similar to F (X). Quick sort sorting is similar to G (X).

Answer 2

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

When the list is small, the overhead for making recursive calls and finding the rotation value, etc. much slower than the iterative process used to sort the insert.

Answer 3

The actual complexity of each sorting algorithm is as follows:

• Best - Insertion Sort: O(N ^ 2), O(N), O(N ^ 2)
• Medium - Fast Qort: O(N ^ 2), O(N log N), O(N log N)
• Worst - Bubble Sort: O(N ^ 2), O(N), O(N ^ 2)