Insertion Sort

Given an array arr[] of n elements, write a function to sort the given array.

Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.

Input:

arr[] = { 5,3,7,1,8,6,9 }

Output:

arr[] = { 1,3,5,6,7,8,9 }

Time Complexity:

O(n^2)