## Insertion Sort

Reference: https://commons.wikimedia.org/wiki/File:Sorting_insertion_sort_anim.gif

The first two elements of the data array are taken into consideration by an Insertion Sort algorithm. A[0] and A[1] are those. Should they be out of sequence, A[0] can be shifted by one spot, allowing A[1] to insert into a vacant space. Next, think about the third component, or A[2] for short. In the event that this element is smaller than A[0], shift A[0], A[1], and A[2] by one position, insert A[2] there, and so on.

A Placement The array is divided into two halves using a sort of array.

1. The array’s first element is the only thing in the sorted portion at first.

2. The remaining components are in the second section.

The elements in the unsorted portion of the array are progressively inserted into the sorted portion of the array, taking their rightful places.

An example of **Insertion Sort**

[15, 7, 11, 4, 2, 5] //Unsorted [15, 7, 11, 4, 2, 5] //A[0] shift one position and insert A[1] to A[0] position(7<15) [7, 15, 11, 4, 2, 5] //A[1] shift one position and insert A[2] to A[1] position(7<11<15) [7, 11, 15, 4, 2, 5] //A[0],A[1],A[2] shift one position and insert A[3] to A[0] position(4<7) [4, 7, 11, 15, 2, 5] [2, 4, 7, 11, 15, 5] [2, 4, 5, 7, 11, 15] //Sorted

**Insertion Sort** Algorithm

insertionSort(A[]){ for (i=0;i<data.length-1;i++){ temp=A[i] Move all elements A[j] grater than temp by one position Place temp in its proper position //Here, Each element A[i] is inserted into its proper position j such that 0≤j≤i } }

**Insertion Sort** running time analysis is at best **O(n)** and at worst **O(n²)**