5 a) Use merge sort to sort 6, 5, 17, 15, 16, 20, 18, 7 into increasing order. Show all the steps in the algorithm (draw the trees as shown in class). b) What is the number of comparisons used in the merge algorithm shown in class to merge the two lists: 5, 6, 7, 12, 15; and 1, 2, 9, 14,16. c) In the merge algorithm, two lists in increasing order are merged into one (longer) list of increasing order. Suppose two (sorted) lists are merged, one has 5 elements, the other has 6. What is the least possible number of comparisons, and when does that occur? What is the maximum possible number of comparisons? 7 a) Count the number of distinct phone numbers, if a valid phone number must have the format NXX-NXX-XXXX where N can be any integer between 3 and 8 inclusive, and X can be any integer between 0 and 9 inclusive. b) How many bit strings of length 20 begin with 11 and end with 00?
The Answer to the Question
is below this banner.
Here's the Solution to this Question
number of ways for N:
number of ways for X:
total number of ways:
Merge sort is a recursive algorithm that continually splits a list in half. If the list is empty or has one item, it is sorted by definition (the base case). If the list has more than one item, we split the list and recursively invoke a merge sort on both halves. Once the two halves are sorted, the fundamental operation, called a merge, is performed. Merging is the process of taking two smaller sorted lists and combining them together into a single, sorted, new list.
Divide the unsorted list into n sublists, each comprising 1 element (a list of 1 element is supposed sorted).
Now, we combine them in exactly the same manner as they were broken down. We first compare the element for each list and then combine them into another list in a sorted manner.
Number of total comparison in merge sort:
Number of total comparison for n = 10:
The minimum number of comparisons for the merge sort occurs, assuming a sane implementation once one of the lists has been fully traversed:
for n= 11:
maximum possible number of comparisons:
Merge sort's best case takes about half as many iterations as its worst case
so, maximum possible number: