Algorithms and Data structures: Merge Sort

This are slides for merge sort

1. 1
Designing algorithms
There are many ways to design an algorithm.
Insertion sortuses an incremental approach: having
sorted the sub-array A[1…j -1], we insert the single
element A[ j] into its proper place, yielding the sorted
sub-array A[1…j].
Another approach to design is the divide-and-conquer
approachwhich has a recursive structureto solve a
given problem;
they break the problem into several sub-problems that are
similar to the original problem but smaller in size,
solve the sub-problems recursively,
and then combinethese solutions to create a solutionto the
original problem.

2. 2
The divide-and-conquer approach
Recursive in structure
Dividethe problem into several smaller sub-
problems that are similar to the original but
smaller in size
Conquerthe sub-problems by solving them
recursively. If they are small enough, just solve
them in a straightforward manner.
Combinethe solutions to create a solution to the
original problem

3. 3
An Example: Merge Sort
Divide: Divide the n-element sequence to be
sorted into two subsequences of n/2
elements each
Conquer:Sort the two subsequences
recursively using merge sort.
Combine:Merge the two sorted
subsequences to produce the sorted answer.

4. 4
Merge Sort
To sort n numbers
if n = 1 done!
recursively sort 2 lists of
numbers n/2and n/2
elements
merge 2 sorted lists in O(n)
time
Strategy
break problem into similar
(smaller) subproblems
recursively solve subproblems
combine solutions to answer

5. 5
Merge Sort cont.
[8, 3, 13, 6, 2, 14, 5, 9, 10, 1, 7, 12, 4]
[8, 3, 13, 6, 2, 14, 5] [9, 10, 1, 7, 12, 4]
[8, 3, 13, 6][2, 14, 5]
[8, 3][13, 6]
[8][3][13][6]
[2, 14][5]
[2][14]
[9, 10, 1] [7, 12, 4]
[9, 10][1]
[9][10]
[7, 12][4]
[7][12]

6. 6
Merge Sort cont.
[3, 8][6, 13]
[3, 6, 8, 13]
[8][3][13][6]
[2, 14]
[2, 5, 14]
[2, 3, 5, 6, 8, 13, 14]
[5]
[2][14]
[9, 10]
[1, 9, 10]
[1]
[9][10]
[7, 12]
[4, 7, 12]
[1, 4, 7, 9, 10,12]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13,14]
[4]
[7][12]

7. 7
Merge Sort Procedure
To sort the entire sequence
A ={A[1], A[2], . . . ,
A[ n]}, we make the initial
call MERGE-SORT( A, 1,
length[ A]), where length[
A] = n.
The procedure MERGE-SORT(A, p, r)sorts the elements
in the sub-array A[ p…r].
The divide step simply computes an index q that partitions
A[ p…r] into two sub-arrays: A[ p…q], containing n/2
elements, and A[ q + 1…r], containing n/2 elements.

8. 8

9. 9
Merge algorithm

10. 10
Merge Sort
The key operation of the merge sort algorithm is the
merging of two sorted sequences in the "combine" step.
To perform the merging, we use an auxiliary procedure
MERGE(A, p, q, r),where A is an array and p, q, and r
are indicesnumbering elements of the array such that p ≤
q < r.
The procedure assumes that the sub-arrays A[ p…q]and
A[ q + 1…r]are in sorted order. It merges them to form a
single sorted sub-array that replaces the current sub-array
A[ p…r].

11. 11
Merge algorithm cont.
The operation of lines 10-17 in the call MERGE(A, 9, 12, 16).

12. 12
Merge algorithm cont.
The operation of lines 10-17 in the call MERGE(A, 9, 12, 16)

13. 13
Analysis of Merge Sort
Statement Effort
So T(n) = (1) when n = 1, and
2T(n/2) + (n) when n > 1
MergeSort(A, left, right) { T(n)
if (left < right) { (1)
mid = floor((left + right) / 2); (1)
MergeSort(A, left, mid); T(n/2)
MergeSort(A, mid+1, right); T(n/2)
Merge(A, left, mid, right); (n)
}
}

14. 14
Analysis of Merge Sort
Divide: computing the middle takes O(1)
Conquer: solving 2 sub-problem takes 2T(n/2)
Combine: merging n-element takes O(n)
Total:
T(n) = O(1) if n= 1
T(n) =2T(n/2)+ O(n)+ O(1) if n> 1
T(n) = O(nlg n)
Solving this recurrence (how?) gives T(n) = O(nlg n)
This expression is a recurrence
To simplify the analysis we assume that the original
problem size is a power of 2. Each divide step then yields
two subsequencesof size exactly n/2.

15. 15
Analysis of Merge Sort cont.
Assume n=2
k
for k>=1
T(n) = 2 T(n/2)+ bn + c
T(n/2) = 2T((n/2) /2) + b(n/2) + c
= 2[2T(n/4) + b(n/2) + c] + bn +c
= 4 T(n/4)+ bn +2c +bn +c
=4 T(n/4) + 2bn+ (1 + 2) c = 2
2
T(n/2
2
)+2bn+(2
0
+2
1
)
= 4 [2T((n/4)/2) + b(n/4) + c] +2bn + (1+2)c
=8 T(n/8) + 3bn+ (1+2+4)c
=2
3
T(n/2
3
) + 3bn+ (2
0
+2
1
+2
2
)c
=2
k
T(n/2
k
)+kbn+(2
0
+2
1
+…+2
k-1
)c
T(1) = a, since n=2
k 
log n = log2
k
= k
T(n) = 2
k
. a + kbn + (2
0
+2
1
+…+2
k-1
) c , but
= b. n log n+ (a + c) n –c
= O (n log n)Worst case