Insertion Sort

Insertion sort is a simple sorting algorithm that repeatedly shifts unsorted elements to the left of the array until it is sorted. The name comes from the process is which a given element is inserted to it’s correct place, one by one.

Process §

Shifting elements in arrays is essentially doing element swaps, which require a third auxiliary variable.

1. Take an array and use a index variable, i to go through the elements of it.
   1. Now, use another index variable j, to go backwards from the element all the way to the first element.
   2. The unsorted element, A[j] is then compared with the element before it (A[j-1]).
      1. If A[j] is greater than A[j-1], then that subarray is sorted. Ignore this element and go to step 1.
      2. If A[j] is smaller, shift left (swap with A[j-1]), decrease j by 1 and repeat step 2.

Pros & Cons §

Pros §

• Very simple to implement.
• Efficient for small data sets
• Other complex algorithms almost sort the array, then employ insertion sort to finish the job

Cons §

• Quadratic time complexity makes it very inefficient on larger datasets

Pseudocode §

Algorithm InsertionSort(A): #A is an unsorted array
	int n <- len(A);
	int i,j;
	For i from 1 to n do:
		For j from i to 0 do: 
			If A[j] >= A[j-1] then:
				i++;
				break;
			Else:
				Swap A[i] and A[i-1];
				j--;
			End If
		End Do
	End Do

	return A;

Complexity Analysis §

Time Complexity §

Worst	Average	Best
$O(n^2)$	$O(n^2)$	$O(n)$

Insertion sort goes through each element of the array, and runs it’s subprocess on them. The best case is when the array is already sorted, in which case the algorithms doesn’t do any swaps and takes $n$ steps to iterate through the array, resulting in $O(n)$.

The worst case is if the array is in descending order. For each element, it has to shift it all the way to front:

$f(n)=1+2+3+\dots n-1=\frac{n(n-1)}{2}$

Why?

$f(n)=1+2+3+\dots n-1$ (First element needs to move 1 step, second needs to move 2, etc.) Now add it to the following function: $f(n)=(n-1)+(n-2)+(n-3)+\cdots +2+1$ (Same thing but reversed)

$2f(n)=n+n+n+\dots n$ (this is done n-1) times $2f(n)=n(n-1)$ $f(n)=\frac{n(n-1)}{2}$

$\frac{n(n-1)}{2}=\frac{1}{2}(n^2-n)=O(n^2)$

Implementation §