Insertion sort analysis

There are different algorithms out there for sorting purposes. They have unique characteristics. Therefore, based on the situation we can choose the most suitable sorting algorithm based on their characteristics. Let’s look at the characteristics of the insertion sort which is one of the simplest sorting algorithms out there.

Inputs: Sequence of n numbers. (Array{A} of n numbers)

Outputs: Reordered input sequence such that a1 ≤ a2 ….. ≤ an where a1, a2 ,……., an represent the n numbers.

Pseudo code

This figure shows the process of the insertion sort algorithm.

One of the most important characteristics of an algorithm is the running time.

Let’s look at the running time of insertion sort.

Running time of algorithm is the execution time of each line of the algorithm. Thus for the insertion sort,

Here for the while loop, running time depends on the condition that is being checked at the run time. Therefore, the total number of times the while loop condition is checked will be t2 +……. + tn (With cost C4) for different j s. Why do we reduce one from the running times of the lines inside the while loop? That is because, the while loop condition is checked once more, than the lines inside the while loop (when the condition is evaluated to false).

Therefore the total running time would be;

Worst case scenario of the insertion sort (When the sequence of numbers are in the reverse sorted order). Then,

since we have to go backward till the beginning every time (have to loop back to the first number of the array A for every j ). Thus, while loop condition will be checked for

times ( equals to 2 + 3 + …….. + n ). And

Then the total running time in the worst case:

That equals to:

Simply an equation of an² + bn + c (quadratic function). Therefore if we consider the rate of growth or the order of growth of the running time, we have to only consider the term an² since the other terms become insignificant for large values of n. The constant a also becomes insignificant when the n is large. So, we say that insertion sort has a worst case running time of θ( n² ) {theta of n-squared}.

Best case running time ( when the sequence of numbers are already sorted):

Then the lines in the while loop will not be executed. Therefore the running time is,

Equals to:

Thus a linear function of n.

Therefore for the same set of two sequences of numbers, insertion sort will take different running times based on the positions numbers are in. Insertion sort takes huge amount of time when the input is very large and numbers are in the reverse sorted order (Or close to reverse sorted order).