All Questions
2
questions
0
votes
0
answers
303
views
Prove that MergeSort is stable for any input size n ∈ N using induction on n.
In terms of a list of objects with two separate fields, suppose a stable sort would order the list in increasing order. However, if two elements have the same number, then they'll appear in the same ...
1
vote
1
answer
601
views
How do I prove by using induction on k, that MergeSort uses $n(\log_2(n)+1)=2^k(k+1)$ comparisons?
I have been asked this question in an assignment for my exam.
The assignment question is: "Assume that Merge uses (exactly) $a+b-1$ comparisons to combine two lists with a and b elements. ...
- 13