All Questions
1
question
2
votes
0
answers
88
views
On bounding the average cost of top-down merge sort
Let $A_n$ be the average number of comparisons to sort $n$ keys by merging them in a top-down fashion (see any algorithm textbook). It can he shown that
$$
A_0 = A_1 = 0;\quad A_n = A_{\lfloor{n/2}\...
