Question

Use a merge sort to sort b, d, a, f, g, h, z, p, o, k into alphabetical order. Show all the steps used by the algorithm.

Short answer

Alphabets are sorted.

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$ and$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

To sort into alphabetical order, firstly the list is split into the two lists

b, d, a, f, g

h, z, p, o, k,

Each of these is sorted by merge sort.

Assume that this has been done.

Then the two lists are a, b, d, f, g,and h, k, o, p, z.

Then these two lists are merged into one sorted list, as follows:

We compare awith hand find that ais smaller; thus acomes first in the merged list, and we pass on to b.

Comparing bwith h,we find that bis smaller, so bcomes next in the merged list, and we pass on

to d.

Repeat this process (using Algorithm 10) until the lists are merged into one sorted list, a, b, d, f, g, h, k, o,p, z.

Returning to the question of how each of the 5-element lists was sorted.

For the list b, d, a, f, g, divide it into the sublists b, d, a,and f, g.Again sort each piece by the same algorithm, producing a, b, d, and f, g,and we merge them into the sorted list a, b, d, f, g.Going one level deeper into the recursion, we see that sorting b, d, and awas accomplished by splitting it into b, d,and a,and sorting each piece by the same algorithm.

The first of these required further splitting into band d.One element list is already sorted.

Similarly, the other 5-element list was sorted by a similar recursive process.

A tree diagram for this problem is displayed below. The top half of the picture is a tree showing the splitting part of the algorithm. The bottom half shows the merging part as an upside-down tree.