Question

Use a merge and sort to sort 4, 3,2,5,1,8,7,6 into increasing order. Show all the steps used by the algorithm.

Short answer

The recursive algorithm is given

Step-by-step solution

Algorithm 10

Algorithm 10 is about the merging of two lists.

Proceduremerge ( $L_1{L}_2$: sorted lists)

L := empty list

While$L_1$ and$L_2$ are both nonempty

Remove smaller of the first element of$L_1$ anddata-custom-editor="chemistry" $L_2$ from its list; put it at the right end of L

If this removal makes one list empty then remove all the elements from the other list and

apprehend them to L

Return L {L is the merged list with elements in increasing order}

Write an algorithm

The tree is shown below.

The inverted tree indicates how the sequence is taken apart and put back together.