2. Consider a list of n distinct numbers (a₁,..., an). Recall that the MERGESORT algorithm sorts this list using O(n log

[answerhappygod]

2 Consider A List Of N Distinct Numbers A An Recall That The Mergesort Algorithm Sorts This List Using O N Log 1 (77.85 KiB) Viewed 12 times

2. Consider a list of n distinct numbers (a₁,..., an). Recall that the MERGESORT algorithm sorts this list using O(n log n) comparisons. Can we do any better (i.e., can we sort a list using asymptotically fewer comparisons in the worst case)? In this problem, we will answer this question in the negative. (a) How many orderings are there of the n numbers? (b) How many orderings are there of the n numbers where a₁ appears before a2? (c) How many orderings are there of the n numbers where a₁ appears before a2 and a3 appears before a4? (d) How many orderings are there of the n numbers where a₁ appears before a2 and a2 appears before az? (e) How many orderings are there of the n numbers where a₁ appears before a2 and a₁ appears before a3?