?38E Use the insertion sort to sort the list in Exercise 34, showing the lists obtained at each step.

Solution In this question we have to use the insertion sort to sort the list 6, 2, 3, 1, 5, 4 step to step. Step 1 Insertion sort : It is a simple sorting algorithm that creates a final sorted list of one item at a time . Here the list is given 6, 2, 3, 1, 5, 4 Using insertion sort on 1st step we get, 2, 6, 3, 1, 5, 4 In first step 2 is shifted towards the left of 6 by insertion. Step 2 2, 6, 3, 1, 5, 4 Using insertion sort on 2nd step we get, 2, 3, 6, 1, 5, 4 In second step 3 is shifted towards the left of 6 by insertion. Step 3 2, 3, 6, 1, 5, 4 Using insertion sort on 3rd step we get, 1, 2, 3, 6, 5, 4 In third step 1 is shifted towards the left of 2 by insertion.