Show the behavior of InsertionSort and MergeSort on input So

Show the behavior of InsertionSort and MergeSort on input <3,8,1,9,2,7,4>.

Solution

Insertion Sort -----Insert one element at one time and ensure that the list is sorted

3 | 8 1 9 2 7 4 Assume that there is only one element in the list ie 3

3 8 | 1 9 2 7 4 Now insert 8 and ensure that 3 and 8 are in sorted order

1 3 8 | 9 2 7 4 Insert 1 in the list so that 1 takes its appropriate position in the sorted list

1 3 8 9 | 2 7 4   

1 2 3 8 9 | 7 4 Insert 2

1 2 3 7 8 9 | 4

1 2 3 4 7 8 9 ------List is sorted

Merge Sort---- It is a divide and conquer algorithm where list is divided into subparts and then those subparts are sorted and then merged into the main large list

3 8 1 9 2 7 4

|

3 8 1 9 2 7 4 divide list into two sublists

| |

3 8 1 9 2 7 4 divide sublists into sub sublists

| | |   

3 8 1 9 2 7 4 lists of one element only

Now start Merging

(3 8) (1 9) (2 7) 4

merge (3 8) (1 9) merge (2 7) (4)

( 1 3 8 9) ( 2 4 7)

merge ( 1 3 8 9) ( 2 4 7)   

1 2 3 4 7 8 9