Consider the following method for rearranging the n distinct numbers x_1,x_2,....x_n in order of increasing size (n is a power of 2). Pair the integers off {x_1,x_2}, {x_3,x_4}, and so forth. Compare each pair and put the smaller number first. Next pair off the pairs into sets of four numbers and merge the ordering pairs to get ordered four-tuples. Continue this process until the whole set is ordered. Find and solve a recurrence relation for the total number of comparisons required to rearrange n distinct numbers. (Hint: First find the number of comparisons needed to merge two ordered K-tuples into ordered 2k-tuples)
I've tried numerous times to solve this problem, but have not yet figured it out. Any help would be greatly appreciated. Thanks..
I've tried numerous times to solve this problem, but have not yet figured it out. Any help would be greatly appreciated. Thanks..