|
Data Structures and Algorithms
with Object-Oriented Design Patterns in C# |
The running time of merge sort is determined by the running time of the recursive Sort method. (The no-arg Sort method adds only a constant amount of overhead). The running time of the recursive Sort method is given by the following recurrence:
where 
.
In order to simplify the solution of Equation 
we shall assume that 
for some integer 
.
Dropping the 
s from the equation we get
which is easily solved by repeated substitution:
Therefore, the running time of merge sort is 
.
Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.
