Hello there, In this article we are going to understand Insertion Sorting or Insertion sort algorithm. It is another simple sorting algorithm. It is more efficient than other quadratic sorting algorithms such as selection and bubble sort.
Performance
It’s best case Performance is : O(n)
It’s Average and worst case performance is equal i.e.: O(n^2)
How Insertion Sort Works
In this sorting algorithm, list is divided in two sub-lists – sorted and unsorted. In each iteration one element is removed from the unsorted list and is placed in its correct position in the sorted list. Hence after each iteration unsorted list gradually shrinks and the sorted keeps on growing. And ultimately all elements became part of sorted list meaning your list is sorted now.
Step by Step Example
Consider an unsorted array A{7 8 3 1 2}. And we are suppose to sort this array in ascending order. So what is the technique used in Insertion sorting . The list is divided in two sub-lists. So let us take first element is sorted list and remaining elements in unsorted list.
7 8 3 1 2, Original list
Sorted : 7
Unsorted : 8 3 1 2, first element selected
Pass 1:
Sorted : 7 8, placed at its correct position
Unsorted : 3 1 2, first element selected
Pass 2:
Sorted : 3 7 8, placed at its correct position
Unsorted : 1 2, first element selected
Pass 3:
Sorted : 1 3 7 8, placed at its correct position
Unsorted : 2, first element selected
Pass 4:
Sorted : 1 2 3 7 8, placed at its correct position
Unsorted : no element left
Here you can see that after 4 passes , our list is get sorted.
Watch this video of Insertion Sort Algorithm
Pseudocode of Insertion Sort
for i = 1 to length(A)
x = A[i]
j = i - 1
while j >= 0 and A[j] > x
A[j+1] ← A[j]
j ← j - 1
end while
A[j+1] = x
end for
Note: Division of Array of List does not mean that we are dividing the list physically. The list is only logically divided.