Insertion Sort

Insertion sort is a type of a sorting algorithm that sorts the list of given items by delivering at least one item in each iteration to its respective place. It is an in-place comparison-based stable sorting algorithm.

Let me elaborate, while insertion sort takes place, the list is divided into two parts. The left end is sorted while the right end is unsorted. At each iteration, one item from the unsorted part is transferred to its correct position in the sorted part.

This is called an incremental design approach since after each iteration we’re one step closer to our solution.

Visualization



This example provides a quick overview of how insertion sort works

The video given below will provide an in-depth explanation.

Pseudo Code

mark first element as sorted
for each unsorted element X
  'extract' the element X
  for j = lastSortedIndex down to 0
    if current element j > X
      move the sorted element to the right by 1
    break the loop and insert X here

Implementation in C++

Time Complexity

In the above code, we run two nested loops and perform comparison and shift operations to sort the input. Let’s find out the worst-case and best-case time complexity:

Worst Case Scenario: This will come into play if the given input list is reverse sorted i.e., in decreasing order. Here, the algorithm performs the maximum number of operations.
Time Complexity = O(n2)

Best Case Scenario: This will come into play if the given input list already sorted i.e., in increasing order. Here, the algorithm performs the minimum number of operations.
Time Complexity = O(n)

Space Complexity

This is an in-place sorting algorithm i.e.; we are not using any extra space for running this algorithm, which implies that
Auxiliary Space = O(1) & Space used by input = O(n)
Total Space Complexity = O(n)

If you find any errors in the article, please comment below.


Written with by Ashwin

Comments

Post a Comment

If you have any doubt, then please feel free to ask.