Insertion sort algorithm implementation

When playing cards, you keep your hand sorted. When you receive a new card, you insert it into its correct position to maintain order.

Similarly, insertion sort works by dividing an array into two parts: a sorted portion and an unsorted portion. It takes elements from the unsorted part one by one and inserts them into their correct position within the sorted part, ensuring that the sorted section remains ordered throughout the process.

The sorted part is similar to the cards already arranged in order. The algorithm takes each item from the unsorted part and inserts it into its correct position within the sorted collection, repeating this process until the entire array is sorted.

Insertion sort pseudocode

Insertion sort steps

image from: AlgoDaily — Fundamental Sorting Algorithms: Bubble and Insertion

Time and Space Complexity

Get Yahia zakaria’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

The time complexity for the insertion sort algorithm is O(N2)

The space complexity is O(1)

When to Use Insertion Sort

• Nearly Sorted Data
• Small Datasets
• Stable Sorting Needed

Implementation

#include<iostream>
using namespace std ;

void insertionsort(int arr[],int n) {
int i, j, key;
   for (j = 1; j < n; j++) {
  key = arr[j];
  i = j - 1;
        while (i >= 0 && arr[i] < key) 
         {
         arr[i + 1] = arr[i];
      i--;
         }
     arr[i + 1] = key;
  }

}

void printarray(int arr[], int n)
{
 for (int i = 0; i < n; i++)
 {
  cout << arr[i] << "  ";
    }
 cout << endl;

}


int main(){

 int arr[] = { 9,2,7,5,1,4,3,6 };
 int n = sizeof(arr) / sizeof(arr[0]);
 insertionsort(arr, n);
 printarray(arr, n);



 system("pause");
 return 0 ;
}