Analysis of Algorithm course

Please print or write neatly

3. Sorting Algorithms: (20 points) Using textbook Figure 2.2 and Figure 2.4 as models to illustrate the operations of Insertion_Sort and Merge_Sort on the array A = 5 6 1 5 (a) 2 2 3 4 4 6 5 1 6 3 1 2 2 5 3 4 4 6 2 4 3 5 4 6 5 1 6 3 (d) 1 2 3 4 5 6 2 4 5 6 1 3 (e) 2 3 4 5 6 1 2 4 5 6 3 (1) | 2 3 4 5 6 1 2 3 4 5 6 Figure 2.2 The operation of INSERTION-SORT on the array A = (5, 2, 4, 6, 1, 3). Array indices appear above the rectangles, and values stored in the array positions appear within the rectangles. (a)-(e) The iterations of the for loop of lines 18. In each iteration, the black rectangle holds the key taken from A[j], which is compared with the values in shaded rectangles to its left in the test of line 5. Shaded arrows show array values moved one position to the right in line 6, and black arrows indicate where the key moves to in line 8. (f) The final sorted array. sorted sequence 1 2 2 3 4 5 6 7 merge | 2 4 5 7 1 2 3 6 merge merge merge initial sequence Figure 2.4 The operation of merge sort on the array A = (5,2,4,7,1,3,2,6). The lengths of the sorted sequences being merged increase as the algorithm progresses from bottom to top