Chapter 1 – Analysis of
Algorithms
Merge Sort
MERGE-SORT A[1 . . n]
If n = 1, done.
Recursively sort A[ 1 . . n/2 ] and A[ n/2+1 . . n ] .
“Merge” the 2 sorted lists.
Key subroutine: MERGE
Merging Two Sorted Arrays
20 12
13 11
7 9
2 1
Merging Two Sorted Arrays
20 12
13 11
7 9
2 1
1
Merging Two Sorted Arrays
20 12 20 12
13 11 13 11
7 9 7 9
2 1 2
1
Merging Two Sorted Arrays
20 12 20 12
13 11 13 11
7 9 7 9
2 1 2
1 2
Merging Two Sorted Arrays
20 12 20 12 20 12
13 11 13 11 13 11
7 9 7 9 7 9
2 1 2
1 2
Merging Two Sorted Arrays
20 12 20 12 20 12
13 11 13 11 13 11
7 9 7 9 7 9
2 1 2
1 2 7
Merging Two Sorted Arrays
20 12 20 12 20 12 20 12
13 11 13 11 13 11 13 11
7 9 7 9 7 9 9
2 1 2
1 2 7
Merging Two Sorted Arrays
20 12 20 12 20 12 20 12
13 11 13 11 13 11 13 11
7 9 7 9 7 9 9
2 1 2
1 2 7 9
Merging Two Sorted Arrays
20 12 20 12 20 12 20 12 20 12
13 11 13 11 13 11 13 11 13 11
7 9 7 9 7 9 9
2 1 2
1 2 7 9
Merging Two Sorted Arrays
20 12 20 12 20 12 20 12 20 12
13 11 13 11 13 11 13 11 13 11
7 9 7 9 7 9 9
2 1 2
1 2 7 9 11
Merging Two Sorted Arrays
20 12 20 12 20 12 20 12 20 12 20 12
13 11 13 11 13 11 13 11 13 11 13
7 9 7 9 7 9 9
2 1 2
1 2 7 9 11
Merging Two Sorted Arrays
20 12 20 12 20 12 20 12 20 12 20 12
13 11 13 11 13 11 13 11 13 11 13
7 9 7 9 7 9 9
2 1 2
1 2 7 9 11 12
Merging Two Sorted Arrays
20 12 20 12 20 12 20 12 20 12 20 12
13 11 13 11 13 11 13 11 13 11 13
7 9 7 9 7 9 9
2 1 2
1 2 7 9 12
11
Time = (n) to merge a total of n elements (linear time).
Analyzing Merge Sort
T(n) MERGE-SORT A[1 . . n]
(1) 1.If n = 1, done.
Abuse
2T(n/2) 2.Recursively sort A[ 1 . . n/2]
3. and A[ n/2+1 . . n ] .
(n) 4.“Merge” the 2 sorted lists
Sloppiness: Should be T( n/2 ) + T( n/2) , but it turns out not
to matter asymptotically.
Recurrence for Merge Sort
(1) if n = 1;
T(n) =
2T(n/2) + (n) if n > 1.
We shall usually omit stating the base case when T(n) = (1)
for sufficiently small n, but only when it has no effect on the
asymptotic solution to the recurrence.
Recursion Tree
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
Recursion Tree
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
T(n)
Recursion Tree
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn
T(n/2) T(n/2)
Recursion Tree
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn
cn/2 cn/2
T(n/4) T(n/4) T(n/4) T(n/4)
Recursion Tree
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn
cn/2 cn/2
cn/4 cn/4 cn/4 cn/4
…
(1)
Recursion Tree
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn
cn/2 cn/2
h = lg n cn/4 cn/4 cn/4 cn/4
…
(1)
Recursion Tree
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn
cn
cn/2 cn/2
h = lg n cn/4 cn/4 cn/4 cn/4
…
(1)
Recursion Tree
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn
cn
cn/2 cn/2 cn
h = lg n cn/4 cn/4 cn/4 cn/4
…
(1)
Recursion Tree
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn
cn
cn/2 cn/2 cn
h = lg n cn/4 cn/4 cn/4 cn/4 cn
…
(1)
Recursion Tree
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn
cn
cn/2 cn/2 cn
h = lg n cn/4 cn/4 cn/4 cn/4 cn
…
(1) #leaves = n (n)
Recursion Tree
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn
cn
cn/2 cn/2 cn
h = lg n cn/4 cn/4 cn/4 cn/4 cn
…
(1) #leaves = n (n)
Total (n lg n)
Conclusions
(n lg n) grows more slowly than (n2).
Therefore, merge sort asymptotically beats insertion sort in
the worst case.
In practice, merge sort beats insertion sort for n > 30 or so.
Question & Answer
08/26/25 30
Thank You !!!
08/26/25 31
