This is an old revision of the document!
Table of Contents
5.1 The Mergesort Algorithm
Mergesort
- Mergesort sorts a given list of numbers by first dividing them into two equal halves, sorting each half separately by recursion, and then combining the results of these recursive calls, in the form of two sorted halves, using the linear time algorithm for merging sorted lists.
- Template for Divide and Conquer Algorithms
- Divide the input into two pieces of equal size; solve the two subproblems on these pieces separately by recursion; and then combine the two results into an overall solution, spending only linear time for the initial division and final recombining.
- Base case for recursion: once the input has been reduced to size 2, we stop the recursion and sort the two elements by simply comparing them to each other
- T(n) denotes its worst case runtime of the template above, O(n) time to divide the input into two pieces, spends T(n/2) to solve each one, O(n) to recombine the solutions from the two recursive calls; runtime T(n) solves following recurrence relation
- T(n) ⇐ 2T(n/2) + cn when n>2; T(2) ⇐ c
- The recurrence relation does not explicitly provide an asymptotic bound on the growth rate of the function T; rather, it specifies T(n) implicitly in terms of its values on smaller inputs.
- To obtain an explicit bound, need to solve the recurrence relation.
Approaches to Solving a Recurrence Relation
- Unroll the recursion: accounting for the runtime across the first few levels, and identify a pattern that can be continued as the recursion expands; then, sum the runtime once all the levels of the recursion to arrive a total runtime
- Substituting a solution: guess for the solution, substitute it into the recurrence relation, check if it works
Unrolling the Mergesort Recurrence
- Analyze the first few levels
- First level: single problem of size n takes at most cn time plus subsequent recursive calls
- Second level: two problems size n/2 each takes time cn/2 (sum of cn) plus subsequent recursive calls
- Third level: four problems of size n/4 each takes time cn/4 (total cn)
- Identify a pattern
- At level j of recursion, number of subproblems doubled j times (now a total of 2^j). Each subproblem has shrunk size by factor of two j times (each size n/2^j so each takes timecn/2^j).
- Level j total runtime: 2^j(cn/2^j) = cn
- Sum over all levels of recursion
- Number of times the input must be halved in order to reduce its size from n to 2 is log2(n)
- Total runtime: O(nlogn)
Substituting a Solution into the Mergesort Recurrence
- T(n) is bounded by O(nlogn); we have agues for the runtime that we want to verify
- T(n) ⇐cnlog2(n) for all n>= 2
- Base case: holds for n = 2
- By induction, T(m) ⇐ cmlog2(m) for all values of m less than n
- Want to establish this for T(n)
- T(n) ⇐ 2T(n/2) + cn ⇐ 2c(n/2)log2(n/2) + cn = cn[log2(n) – 1] + cn = cnlog2(n) – cn + cn = cnlog2(n)
- This establishes what we want for T(n)
An Approach Using Partial Substitution
- Somewhat weaker kind of substitution one can do, in which guesses the overall form of the solution without pinning down the exact values of all the constant and other parameters at the outset
- Method can actually be useful in working out the exact constant when one has some guesses of the general form of the solution
