PART A
(PART A: TO BE REFFERED BY STUDENTS)
Experiment No.02
A.1 Aim:
Write a program to implement Merge sort using Divide and Conquer Approach
and analyze its complexity.
A.2 Prerequisite:
A.3 Outcome:
After successful completion of this experiment students will be able to analyze the
time complexity of various classic problems.
A.4 Theory:
Merge sort is based on the divide-and-conquer paradigm. Its worst-case running
time has a lower order of growth than insertion sort. Since we are dealing with
subproblems, we state each subproblem as sorting a subarray A[p .. r]. Initially, p =
1 and r = n, but these values change as we recurs through subproblems.
To sort A[p .. r]:
1. Divide Step
If a given array A has zero or one element, simply return; it is already sorted.
Otherwise, split A[p .. r] into two subarrays A[p .. q] and A[q + 1 .. r], each
containing about half of the elements of A[p .. r]. That is, q is the halfway point
of A[p .. r].
2. Conquer Step
Conquer by recursively sorting the two subarrays A[p .. q] and A[q + 1 .. r].
3. Combine Step
Combine the elements back in A[p .. r] by merging the two sorted
subarrays A[p .. q] and A[q + 1 .. r] into a sorted sequence. To accomplish this
step, we will define a procedure MERGE (A, p, q, r).
• Algorithm:
MERGE (A, p, q, r)
n1 ← q − p + 1
n2 ← r − q
Create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1]
FOR i ← 1 TO n1
DO L[i] ← A[p + i − 1]
FOR j ← 1 TO n2
DO R[j] ← A[q + j ]
L[n1 + 1] ← ∞
R[n2 + 1] ← ∞
i←1
j←1
FOR k ← p TO r
DO IF L[i ] ≤ R[ j]
THEN A[k] ← L[i]
i←i+1
ELSE A[k] ← R[j]
j←j+1
• Time Complexity:
In sorting n objects, merge sort has an average and worst-case
performance of O(n log n). If the running time of merge sort for a list of
length n is T(n), then the recurrence T(n) = 2T(n/2) + n follows from the definition
of the algorithm (apply the algorithm to two lists of half the size of the original list
and add the n steps taken to merge the resulting two lists). The closed form follows
from the master theorem.
In the worst case, the number of comparisons merge sort makes is equal to or
slightly smaller than (n ⌈lg n⌉ - 2⌈lg n⌉ + 1), which is between (n lg n - n + 1) and
(n lg n + n + O(lg n)).
Time complexity=O(nlogn)
•
PART B
(PART B: TO BE COMPLETED BY STUDENTS)
(Students must submit the soft copy as per following segments within two hours of the
practical. The soft copy must be uploaded on the Blackboard or emailed to the
concerned lab in charge faculties at the end of the practical in case the there is no Black
board access available)
Roll No.:C Name:
Class: SE Batch: C
Date of Experiment Date of Submission:
Grade:
B.1 Software Code written by student:
(Paste your code completed during the 2 hours of practical in the lab here)
CODE:-
#include <stdio.h>
void merge_sort(int i, int j, int a[], int aux[]) {
if (j <= i) {
return;
int mid = (i + j) / 2;
merge_sort(i, mid, a, aux);
merge_sort(mid + 1, j, a, aux);
int pointer_left = i;
int pointer_right = mid + 1;
int k;
for (k = i; k <= j; k++) {
if (pointer_left == mid + 1)
aux[k] = a[pointer_right];
pointer_right++;
} else if (pointer_right == j + 1)
aux[k] = a[pointer_left];
pointer_left++;
} else if (a[pointer_left] < a[pointer_right])
aux[k] = a[pointer_left];
pointer_left++;
} else
aux[k] = a[pointer_right];
pointer_right++;
for (k = i; k <= j; k++)
{
a[k] = aux[k];
int main() {
int a[100], aux[100], n, i, d, swap;
printf("Enter number of elements in the array:\n");
scanf("%d", &n);
printf("Enter %d integers\n", n);
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
merge_sort(0, n - 1, a, aux);
printf("Printing the sorted array:\n");
for (i = 0; i < n; i++)
printf("%d\n", a[i]);
return 0;
B.2 Input and Output:
B.3 Observations and learning:
(Students are expected to comment on the output obtained with clear observations and
learning for each task/ sub part assigned)
We understood the implementation of the Merge sort.
B.4 Conclusion:
(Students must write the conclusion as per the attainment of individual outcome listed
above and learning/observation noted in section B.3)
We demonstrated Merge Sort and found out its complexity.
B.5 Question of Curiosity
(To be answered by student based on the practical performed and learning/observations)
Q1: Derive time complexity of merge sort?
Ans:
Merge sort works by dividing nodes in half at each level until the number of
nodes becomes 1, hence total number of times we would need to do this
would be [log2n] and for each level we perform O(n) work, hence total time
taken will bw O(nlogn).
Q2: What is worst case and best case time complexity of merge sort?
Ans:
Worst case time complexity of merge sort is O(nlogn).
Best case time complexity of merge sort is O(nlogn).
Q3: How many comparisons are done in merge sort?
Ans:
When we run out of the elements in one of the lists, we put the remaining
elements into the last slots of the sorted list. As a result, merging two lists
which have a total of n elements that requires at most n-1 comparisons.
Q4: Can we say merge sort works best for large n? Yes or no? Reason?
Ans:
No merge sort is not best for n numbers or for large numbers.
This is because it has a consistent speed of execution on any size of data,
mostly preferred for linked lists and has worst case of O(nlogn).
************************
