SRI RAMAKRISHNA ENGINEERING
COLLEGE
[Educational Service : SNR Sons Charitable Trust]
[Autonomous Institution, Reaccredited by NAAC with ‘A+’ Grade]
[Approved by AICTE and Permanently Affiliated to Anna University, Chennai]
[ISO 9001:2015 Certified and all Eligible Programmes Accredited by NBA]
VATTAMALAIPALAYAM, N.G.G.O. COLONY POST, COIMBATORE – 641 022.
partment of Artificial Intelligence and Data Scie
epartment
20IT254 – DESIGN AND ANALYSIS OF ALGORITHMS
Presentation By,
[Link] Sankari
AP/AI&DS
20IT254 – DESIGN AND ANALYSIS OF
ALGORITHMS
Module I : INTRODUCTION TO ANALYSIS OF
ALGORITHMS 12
Basics of Algorithm and Mathematics: Algorithm –
Mathematical notation – Efficiency of algorithm – Asymptotic
notation – Analysis of Algorithm: Analyzing control structures –
Solving recurrence – Divide and Conquer: Long Integer
Multiplication – Binary search – Quick Sort – Merge Sort.
20IT254 - DESIGN AND ANALYSIS OF ALGORITHM
Sorting
Sorting
a very classic problem of reordering
items (that can be compared, e.g.,
integers, floating-point numbers,
strings, etc) of an array (or a list) in
a certain order increasing, non-
decreasing lexicographical
20IT254 - DESIGN AND ANALYSIS OF ALGORITHM
Merge Sort
Merge Sort
• Merge sort follows divide and conquer technique
• In dividing phase, the problem is divided into smaller problem and solved recursively
• In conquering phase, partitioned array is merged together recursively
• Merge sort applied to first half and second half of array
• This given two sorted halves, which can then be recursively merged together
20IT254 - DESIGN AND ANALYSIS OF ALGORITHM
Merge Sort
Three Steps:
◦ Divide: Partition array into two sub list s1 and s2 with n/2
elements each
◦ Conquer: Then sort sub list s1 and s2
◦ Combine: Merge s1 and s2 into unique sorted group
20IT254 - DESIGN AND ANALYSIS OF ALGORITHM
Steps involved in Merge
sort
1. Take two input arrays B and C, and an output array A
2. The first element of B and C array are compared, then smaller element is stored in
output array A and corresponding pointer incremented
3. When either input array is exhausted the remainder of other array is copied to output
array A
20IT254 - DESIGN AND ANALYSIS OF ALGORITHM
Example
51, 13, 10, 64, 34, 5, 32, 21
we want to sort these 8 numbers,
divide them into two halves
20IT254 - DESIGN AND ANALYSIS OF ALGORITHM
51, 13, 10, 64, 34, 5, 32, 21
51, 13, 10, 64 34, 5, 32, 21
divide these similarly for
4 numbers these 4
into halves
20IT254 - DESIGN AND ANALYSIS OF ALGORITHM
51, 13, 10, 64, 34, 5, 32, 21
51, 13, 10, 64 34, 5, 32, 21
51, 13 10, 64 34, 5 32, 21
51 13 10 64 34 5 32 21
merge pairs of single
number into a
sequence of 2 sorted
numbers
20IT254 - DESIGN AND ANALYSIS OF ALGORITHM
51, 13, 10, 64, 34, 5, 32, 21
51, 13, 10, 64 34, 5, 32, 21
51, 13 10, 64 34, 5 32, 21
51 13 10 64 34 5 32 21
13, 51 10, 64 5, 34 21, 32
then merge again into
sequences of 4 sorted
numbers
20IT254 - DESIGN AND ANALYSIS OF ALGORITHM
51, 13, 10, 64, 34, 5, 32, 21
51, 13, 10, 64 34, 5, 32, 21
51, 13 10, 64 34, 5 32, 21
51 13 10 64 34 5 32 21
13, 51 10, 64 5, 34 21, 32
10, 13, 51, 64 5, 21, 32, 34
20IT254 - DESIGN AND ANALYSIS OF ALGORITHM
51, 13, 10, 64, 34, 5, 32, 21
51, 13, 10, 64 34, 5, 32, 21
51, 13 10, 64 34, 5 32, 21
51 13 10 64 34 5 32 21
13, 51 10, 64 5, 34 21, 32
10, 13, 51, 64 5, 21, 32, 34
5, 10, 13, 21, 32, 34, 51, 64
20IT254 - DESIGN AND ANALYSIS OF ALGORITHM
Merge sort Steps
1. Divide: Dividing a sequence of n numbers into two smaller sequences is
straightforward
2. Conquer: Merging two sorted sequences of total length n can also be done
easily, at most n-1 comparisons
20IT254 - DESIGN AND ANALYSIS OF ALGORITHM
10, 13, 51, 64 5, 21, 32, 34
Result:
To merge two sorted sequences,
we keep two pointers, one to each sequence
Compare the two numbers pointed,
copy the smaller one to the result
and advance the corresponding pointer
10, 13, 51, 64 5, 21, 32, 34
Result: 5,
Then compare again the two numbers
pointed to by the pointer;
copy the smaller one to the result
and advance that pointer
10, 13, 51, 64 5, 21, 32, 34
Result: 5, 10,
Repeat the same process …
10, 13, 51, 64 5, 21, 32, 34
Result: 5, 10, 13
Again …
10, 13, 51, 64 5, 21, 32, 34
Result: 5, 10, 13, 21
and again …
10, 13, 51, 64 5, 21, 32, 34
Result: 5, 10, 13, 21, 32
…
10, 13, 51, 64 5, 21, 32, 34
Result: 5, 10, 13, 21, 32, 34
When we reach the end of one sequence,
simply copy the remaining numbers in the
other sequence to the result
10, 13, 51, 64 5, 21, 32, 34
Result: 5, 10, 13, 21, 32, 34, 51, 64
Then we obtain the final sorted sequence
Merge Sort Example
8 3 2 9 7 1 5 4
8 3 2 9 7 1 5 4
8 3 2 9 71 5 4 The non-recursive version of Merge
sort starts from merging single
elements into sorted pairs.
8 3 2 9 7 1 5 4
3 8 2 9 1 7 4 5
2 3 8 9 1 4 5 7
1 2 3 4 5 7 8 9
Example
Example
Example
20IT254 - DESIGN AND ANALYSIS OF ALGORITHM
20IT254 - DESIGN AND ANALYSIS OF ALGORITHM
Analysis
In merge sort 2 recursive calls are made. Each recursive call focuses on n/2
elements of the list.
After 2 recursive calls one call is made to combine two sub lists i.e., to
merge all n elements.
Time taken by right
sub list to get sorted Time taken for
combining two sublists
T(n)= T(n/2) + T(n/2) + cn
Time taken by left
sub list to get sorted
20IT254 - DESIGN AND ANALYSIS OF ALGORITHM
Analysis
2
methods
20IT254 - DESIGN AND ANALYSIS OF ALGORITHM
Masters theorem
T(n) = T(n/2)+T(n/2)+c
when n>1 , T(1) = 0
Using Masters Theorem,
T(n) = 2T(n/2) + c(n)
a=2 b=2 k=1 p=0
a= bk => 2= 2
Case 2 If p > -1, then T(n) = θ ([Link]+1n)
T(n) = θ (nlog22.log0+1n)
T(n) =θ (n log n)
20IT254 - DESIGN AND ANALYSIS OF ALGORITHM
Using Substitution Method
20IT254 - DESIGN AND ANALYSIS OF ALGORITHM
Using Substitution Method
20IT254 - DESIGN AND ANALYSIS OF ALGORITHM
Analysis/Complexity of Merge
Sort
Best case: O(n log n)
Average case : O(n log n)
Worst case: O(n log n)
20IT254 - DESIGN AND ANALYSIS OF ALGORITHM
20IT254 - DESIGN AND ANALYSIS OF ALGORITHM