Insertion Sort

Sorting has always been a crucial operation in computer science and in this article, we will be learning about the Insertion Sort.

Insertion Sort is similar to sorting a hand of cards. This means that we start with one card and gradually insert the remaining cards into their correct positions.

The Problem Statement is as follows:

Given an array of N integers, sort the elements of the array using the Insertion Sort algorithm.

Example:

Input: N = 4, array[] = {1,11,7,4}

Output: 1,4,7,11

Insertion Sort Algorithm:

• Start from the second element of the array.

• Compare the second element with the first one. If the second element is smaller, swap them. Else we keep them as they are.

• Move to the third element and compare it with the elements to its left (1st and 2nd) that are present in the sorted part of the array. This will insert the third element into the correct position in the sorted part.

• Continue this process for every element until the entire array is sorted.

Insertion Sort Code in C++:

Time complexity: O(N^2)

Space Complexity: O(1)