Sorting closed

Question

Consider the following two statements:
P: There exists a comparison sort of 5 numbers that uses at most 6 comparisons in worst case.
Q: Heap sort can be used as the auxiliary sorting routine in radix sort, because it operates in-place

Choose appropriate option.

• A. P true, Q false
  
• B. Q true, P false
  
• C. Both P, Q are true
  
• D. Both P, Q are false

Comments

Auxiliary sorting of heap sort

why not stable?

---

The auxiliary sorting routine in radix sort needs to be stable, meaning that numbers with the same value appear in the output array in the same order as they do appear in the input array. Heapsort is not stable. It does operate in place, meaning that only a constant number of elements of the input array are ever stored outside the array.

---

yes, option D is correct

Answer 1

P is False because of the number of leaves of a decision tree which sort $5$ numbers is $5!$ and the height of a tree is atleast  $log(5!)$. We need atleast $7$ comparisons. 

Q is False because of auxiliary sorting routine in radix sort needs to be stable, meaning that numbers with the same value appear in the output array in the same order as they do appear in the input array. Heapsort is not stable. It does operate in place, meaning that only a constant number of elements of the input array are ever stored outside the array

Comments

can you explain about P statement in solution?how did you get 7.not getting?