I have the following problem: As we saw in class, if you want to sort 3 values u

Question

I have the following problem:

As we saw in class, if you want to sort 3 values using a comparison-based sort, you cannot beat 3 comparisons, worst case. Suppose that you had a special, hardware based comparison, that compared 3 values at once, and gave an output based on which permutation of the items was given. How many comparisons, in the worst case, would the same argument give you, for sorting 6 items? Show any calculations. (Note, you do not need to actually try to give any sorting algorithm, only use the lower-bound argument.)

Explanation / Answer

We can use a similar approach to merge sort (which has a very predictable run time of n log n). But instead of grouping 2 values as in merge sort, here we group 3 values at a time.

The k groups of 3 values are sorted in kO(1) time.

But during merging, we can't compare 3 values at a time anymore. We have to compare 2 values.

So, for 6 numbers form two groups of 3 values each and sort them using special comparator.

This takes 2 comparisons.

Then to merge two sorted groups of 3 values each, we need 5 comparisons of two values in worst case.

So, total of 5+2 = 7 comparisons are needed to sort 6 values using the special hardware.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---