CS212: Design & Analysis of Algorithms 3rd Semester
Lecture 5: August 12
Instructor: Prof. Prateek Vishnoi Indian Institute of Technology, Mandi
5.1. Merging problem
Input : Two sorted arrays A and B.
Output : Single sorted array C which contains all elements of A and B.
First Approach
Simply combine the arrays and then sort.
Analysis
Since best sorting algorithm that is known today is O(n log n), thus copying the arrays and sorting would
require O(n) + O(n log n) = O(n log n). Again the most famous question comes
Can we do better ??
Second thought
Compare the first element of both the arrays and place the minimum in the third array. Move towards the
next element of the copied array. Repeat the process until one of the array is exhausted. After that copy the
second remaining array in the third one.
Recurrence Relation
We assume that, both the arrays contain n elements, then
T (n, n) = T (n − 1, n) + c
OR
T (n, n) = T (n, n − 1) + c
T (0, n) = nc
T (n, 0) = nc
5-1
5-2 Lecture 5: August 12
Pseudo code
Algorithm 1 Merge Two Sorted Arrays
1: procedure MERGE(A,B)
2: Initialize pointers i ← 0, j ← 0
3: Initialize empty array C
4: while i < length(A) and j < length(B) do
5: if A[i] < B[j] then
6: Append A[i] to C
7: i←i+1
8: else
9: Append B[j] to C
10: j ←j+1
11: end if
12: end while
13: while i < length(A) do
14: Append A[i] to C
15: i←i+1
16: end while
17: while j < length(B) do
18: Append B[j] to C
19: j ←j+1
20: end while
21: Return C
22: end procedure
Recurrence Tree
T (n, n)
T (n − 1, n) T (n, n − 1) −−−−−−−−−−−−−−− c
T (n − 2, n) T (n − 1, n − 1) T (n − 1, n − 1) T (n, n − 2) −−−−−−−−−− c
According to recurrence relation, only one of the path from root to leaf will be followed. It can be easily
checked that the height of the recurrence tree is O(n) and when combined with termination step it results
in O(n)
Best Case : Time Complexity = Ω(n)
Worst Case : Time Complexity = O(n)
Average Case : Time Complexity = O(n)
Since all T.C are equal we can safely write
Time Complexity = Θ(n)
Lecture 5: August 12 5-3
5.2. Merge Sort
Now we will move forward to the merge sort algorithm which is our first O(n log n) time complexity algorithm.
Input : An array A of n integers.
Output : Return sorted array A.
Merge Sort is a classic divide-and-conquer algorithm used to sort an array or list. The basic idea behind
merge sort is to divide the array into two smaller subarrays until each subarray contains a single element,
and then merge those subarrays in a way that results in a sorted array.
Steps of Merge Sort
Divide: Recursively split the array into two halves until each half contains a single element.
Conquer: Recursively sort each half.
Combine: Merge the sorted halves to produce the final sorted array.
Pseudo code
Algorithm 2 Merge Sort
1: procedure MergeSort(arr)
2: if length(arr)
j > 1 then
k
length(arr)
3: mid = 2
4: left half = arr[1:mid]
5: right half = arr[mid+1:length(arr)]
6: MergeSort(left half)
7: MergeSort(right half)
8: arr = Merge(left half, right half)
9: end if
10: return arr
11: end procedure
Example
Let an unsorted array A = [11,31,25,8,37,17,40,49]. We now show the different steps of merge sort on the
following input with the help of a diagram.
5-4 Lecture 5: August 12
Recurrence Relation
(
2T ( n2 ) + cn if n > 1
T (n) =
c if n = 1
Time Complexity Analysis
Best Case : Time Complexity = Ω(n log n)
Worst Case : Time Complexity = O(n log n)
Average Case : Time Complexity = O(n log n)
Since all T.C are equal we can safely write
Time Complexity = Θ(n log n)
Space Complexity
Since we are using an extra array in merging the sorted arrays and some constant variables, thus
Space complexity = O(n)
Lecture 5: August 12 5-5
Judgment Question
Will it result in better time complexity asymptotically, if we divide the array in three equal parts instead of
two? Why or Why not?
Discussed in class.
5.3. Practice Questions
Is Merge sort a stable sort?
Design a O(n log n) time algorithm that, given a set S of n integers and another integer x determines
whether or not there exists two integers in set S such that whose sum equals x. Do the complete analysis.
Discussed in class.
Let A[1 . . . n] be an array of n distinct integers. If i < j and A[i] > A[j] then the pair (i,j) is called
an inversion of A. Give an algorithm that determines the number of inversions in a permutation of n
elements in O(n log n) time in worst case scenario. Do the complete analysis.
