What is the Insertion Sort ?
Insertion Sort is a simple and intuitive comparison-based sorting algorithm. It builds the final sorted array one element at a time. It is much like sorting playing cards in yours hands; you take on card and insert it into its correct position relative to the already sorted cards.
Key Characteristics
- Time Complexity : – O(n2) in the worst case and average case: O(n) in the best case when the array is already sorted. ‘
- Space Complexity : – O(1) : (in place sorting)
- Stability : – Stable (does not change the relative order of equal elements).
- Algorithm Type : – Comparison-Based Sorting
How Insertion Sort Work ???
- Start with the First Element.
- Consider the First Element as Sorted.
- Insert the next element into sorted portion.
- Take the next element from the unsorted portion.
- Compare it with the element in the sorted portion.
- Shift the element in the sorted portion to the right to make space for the new element.
- Insert the new element in the correct position.
- Repeat
- Move to the next element and repeat in its process until the entire array is sorted.
Steps and Example
Consider the Following unsorted array: –
[5, 3, 8, 4, 2]Pass 1
- The First Element “5” is already sorted.
Pass 2
- Take “3” and Compare it with “5”.
- Since “3” is smaller than “5”, insert “3” before “5”.
- Array Now : [3, 5, 8, 4, 2]
Pass 3
- Take “8” and compare it with “5”.
- Since “8” is larger than “5”, it remains in its position.
- Array Now : [3, 5, 8, 4, 2]
Pass 4
- Take “4” and compare it with “8”.
- Since “4” is smaller than “8”, move “8” to the right.
- Compare “4” with “5”, since “4” is smaller, move “5” to the right.
- Insert “4” before “5”.
- Array Now : [3, 4, 5, 8, 2]
Pass 5
- Take “2” and compare it with “8”.
- Since “2” is smaller than “8”, move “8” to the right.
- Compare “2” with “5”, since “2” is smaller, move “5” to the right.
- Compare “2” with “4”, since “2” is smaller, move “4” to the right.
- Insert “2” before “3”.
- Array Now : [2, 3, 4, 5, 8]