Insertion sort explanation

 Insertion sort is one of the best sorting techniques and it is more efficient than even quick sort and merge sort when it comes to sort the already sorted data structure.

Insertion sort is used for sorting the data structures in any order and it is considered as one of the efficient sorting techniques.

Now what insertion sort does is, it makes a window between y and 0 and all the numbers between y and 0 are sorted. Y is increasing and with increment of y, z is decreasing to sort the array from 0 to y.

 

y=1

while y<5

z=y-1

num=x[y]

while z>=0 && arr[z]>num

x[z+1]=x[z]

z--

inner loop ends here

x[z+1]=num;

y++

while loop ends here

arr = {1,3,4,6,0}

Iteration 1 : 

y=1

num=arr[y]=3

z=y-1

as it will not go into inner loop as arr[z]<num means from 0 to y, values are sorted

nothing will be altered

Iteration 2 : 

y=2

num=arr[2]=4

z=y-1

as it will not go into inner loop as arr[z]<num means from 0 to y, values are sorted

nothing will be altered

Iteration 3 : 

y=3

num=arr[2]=6

z=y-1

as it will not go into inner loop as arr[z]<num means from 0 to y, values are sorted

nothing will be altered

Iteration 4 : 

y=4

num=0

z=3 (y-1)

Iteration starts for Z

inner Iteration 1 : 

z=3

num=0

arr = {1,3,4,6,6}

inner Iteration 2 : 

z=2

num=0

arr = {1,3,4,4,6}

inner Iteration 3 : 

z=1

num=0

arr = {1,3,3,4,6}

inner Iteration 4 : 

z=0

num=0

arr = {1,1,3,4,6}

inner iteration terminated as z=-1

x[z+1]=num;

means x[0]=0;

arr = {0,1,3,4,6}

Array is sorted.