Question

Sort the array A = [ 3, 1, 4, 1, 5, 9, 2, 6, 5] using insertion sort and illustrate your solution?

Answer 1

Answer:

Sorted list : [1, 1, 2, 3, 4, 5, 5, 6, 9]

Explanation:

For j= 2 to length of A

we find the place for A[j] in the sub-array A[1,..., j]

Taking i from j-1 to 1, if A[i] is greater than A[j] we shift it to right.