Page 225 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes The following figure illustrates this algorithm by sorting a list of keys associated with a binary
tree in descending order. Each node of the tree represents a recursive call of mergesort, and the
list is divided there.

Did u know? When we traverse back to the node, the sublists are merged in the required
order.

Figure 13.3: Merge Sort

Source: http://ee.sjtu.edu.cn/po/Class-web/data-stucture/csc120ch9.pdf
Note that : It will group 2 sorted sublists and form 1 sorted list
: Sorted sublist

Let us see a step by step example of merge sort:

Example: Having the following list, let’s try to use merge sort to arrange the numbers
from lowest to greatest:

Unsorted list: 50, 81, 56, 32, 44, 17, 99
Divide the list in two: the first list is 50, 81, 56, 32 and the second is 44, 17, 99.
Divide again the first list in two which results: 50, 81 and 56, 32.
Divide one last time, and will result in the elements of 50 and 81. The element of 50 is just one,
so you could say it is already sorted. 81 is the same one element so it’s already sorted.
Now, It is time to merge the elements together, 50 with 81, and it is the proper order.
The other small list, 56, 32 is divided in two, each with only one element. Then, the elements are
merged together, but the proper order is 32, 56 so these two elements are ordered.
Next, all these 4 elements are brought together to be merged: 50, 81 and 32, 56. At first, 50 is
compare to 32 and is greater so in the next list 32 is the first element: 32 * * *. Then 50 is again
compared to 56 and is smaller, so the next element is 50: 32 50 * *. The next element is 81, which
is compared to 56, and being greater, 56 comes before, 32 50 56 *, and the last element is 81, so the
list sorted out is 32 50 56 81.

218 LOVELY PROFESSIONAL UNIVERSITY