Merge sort Problem ??
Computer Science
Level
3
You are running an arm-wrestling competition with four contestants. When two contestants are matched, the strongest one always wins, and there are no ties. Using Merge Sort, how many matches are needed to sort the competitors from weakest to strongest?
4 matches
4 or 5 matches, depending on the outcome of certain matches
5 matches
6 matches
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Merge sort divides the list into n sublists, each containing 1 element. It then repeatedly merges the sublists to produce a new sorted sublist until there is only 1 list remaining that is completely sorted.
For 4 elements, first compare the first two and last two elements. This will take 2 steps to sort them into 2 lists of 2 elements each. Then merge them into a list of 4 elements. Depending on whether the lists are already sorted or if one change has to be made, there are either 2 steps or 3. So the total comes to 5 steps.