Why is Insertion sort better than Quick sort for small list of elements?

algorithm quicksort insertion-sort
user1031752 picture user1031752 · Nov 12, 2011 · Viewed 43.9k times · Source

Isn't Insertion sort O(n^2) > Quicksort O(n log n)...so for a small n, won't the relation be the same?

Answer

Casey Robinson picture Casey Robinson · Nov 12, 2011

Big-O Notation describes the limiting behavior when n is large, also known as asymptotic behavior. This is an approximation. (See http://en.wikipedia.org/wiki/Big_O_notation)

Insertion sort is faster for small n because Quick Sort has extra overhead from the recursive function calls. Insertion sort is also more stable than Quick sort and requires less memory.

This question describes some further benefits of insertion sort. ( Is there ever a good reason to use Insertion Sort? )

Related questions

How to sort an array in a single loop?

So I was going through different sorting algorithms. But almost all the sorting algorithms require 2 loops to sort the array. The time complexity of Bubble sort & Insertion sort is O(n) for Best case but is O(n^2) as …

Read More
How to optimize quicksort

I am trying to work out an efficient quicksort algo. It works okay, but takes long time to run when the number of elements are huge, and certain sections of the array are pre-sorted. I was looking up the Wikipedia …

Read More
Quicksort with Python

I am totally new to python and I am trying to implement quicksort in it. Could someone please help me complete my code? I do not know how to concatenate the three arrays and printing them. def sort(array=[12,4,5,6,7,3,1,15]): less = [] …

Read More