The running time of merge sort is determined by the running
time of the recursive `DoSort` routine.
(The main `DoSort` only adds a constant amount of overhead).
The running time of the recursive `DoSort` routine 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 © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.