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

## 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(n

^{2})

**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.

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

Nice 👍

ReplyDelete