InsertionSort

Insertion sort is similar to sorting playing cards.
Start with second element and keep in correct location to its left.
Only difference in programming is all the other elements need to be moved to the right to make place for the incoming element.
It is particularly useful for partially sorted array.

Time complexity : O(n2)
Extra Memory:θ(1)
Stable : Yes

	#include<iostream>
	using namespace std;
	void print(int*arr, int size)
	{
	for (int i = 0; i < size; i++) {
	cout << arr[i] << " " ;
	}
	cout << endl;
	}
	void insertionsort(int*arr, int size)
	{
	for (int i = 1; i < size; i++)
	{
	int key = arr[i];
	int j = i - 1;
	while (j >= 0 && arr[j] > key) {
	arr[j + 1] = arr[j];
	j--;
	}
	arr[j + 1] = key;
	print(arr, size); //just to see what happens after every iteration
	}
	}
	int main()
	{
	int arr[] = { 5,4,3,2,1 };
	insertionsort(arr, 5);
	return 0;
	}

view raw insertionsort.cpp hosted with ❤ by GitHub