# Insertion Sort

Insertion sort : Pick an element in the array and position it in its appropriate place in the natural ordering.

e.g. Array 5,4,3,2,1

Pass 1:

Input : 5,4,3,2,1

4 is lesser than 5, so re-position 4.

Output: 4,5,3,2,1

Pass 2:

Input :4,5,3,2,1

3 is lesser than 4, so re-position 3.

Output: 3,4,5,2,1

Pass 3:

Input :3,4,5,2,1

2 is lesser than 3, so re-position 3.

Output: 2,3,4,5,1

Pass 4:

Input :2,3,4,5,1

1 is lesser than 2, so re-position 2.

Output: 1,2,3,4,5

Array is now sorted.

So, the complexity of the sorting lies in re positioning the array elements.

• Worst case: O.
• Best case: O.
• Average case for a random array: O.

I have written a small program to compare the elements using insertion sort algorithm.

public class InsertionSort
{
public static void main(String[] args)
{
int arr[] = {28,26,1,7,13,12,9,-1,6,6,6,6,5,6,4,3,2,1};

for(int i = 1 ; i < arr.length ; i++)
{
if(arr[i] < arr[i-1])
{
boolean shift = false;
int temp = -100;
for(int j = 0 ; j <= i ; j++)
{

if(shift)
{
int temp1 = arr[j];
arr[j] = temp;
temp = temp1;
continue;
}

if(arr[j] > arr[i])
{
temp = arr[j];
arr[j] = arr[i];
shift = true;
}
}
}
}

for(int i : arr)
{
System.out.println(i);
}
}
}



Stay well and happy coding 🙂