Looking back at mergesort

For mergesort the recurrence relation is

T(N) = 1 if N == 1
T(N) = cn + 2T(N/2) if N != 1

so if we draw the recursion tree for such a recurrence relation we get
Height of tree = lg N
Number of leaves = N
--------------
Leaves at level 0 -> 1
Leaves at level 1 -> 2
Leaves at level 2 -> 4
Leaves at level 3 -> 8
...
Leaves at level lg N -> N

Total Work Done
----------------
Work done at level 0 -> cn
Work done at level 1 -> cn
Work done at level 2 -> cn
....
Work done at level lg N -> cn

So total work done => cn * lg N => O(n lg n)