(b) You are given four numbers a, b, c, d. You want to sort them in...

Transcribed Image Text:

(b) You are given four numbers a, b, c, d. You want to sort them in increasing order. It is known that they are all different, and furthermore a <b and c <d. Only comparison-based sorting is allowed. i. Prove a worst-case lower bound of 3 on the number of comparisons needed to sort the numbers. [4 marks] ii. Give an algorithm, in the form of a decision tree, that sorts the numbers in the worst- case optimal number of comparisons. [6 marks] (b) You are given four numbers a, b, c, d. You want to sort them in increasing order. It is known that they are all different, and furthermore a <b and c <d. Only comparison-based sorting is allowed. i. Prove a worst-case lower bound of 3 on the number of comparisons needed to sort the numbers. [4 marks] ii. Give an algorithm, in the form of a decision tree, that sorts the numbers in the worst- case optimal number of comparisons. [6 marks]

Answer rating: 100% (QA)

i To prove a worstcase lower bound of 3 on the number of comparisons needed to sort the numbers a b ... View the full answer