Department of Computer Engineering

Experiment No.3
Aim: To study and implement divide and conquer technique using Merge sort
Theory:
Merge sort is defined as a sorting algorithm that works by dividing an array into
smaller subarrays, sorting each subarray, and then merging the sorted subarrays back
together to form the sorted array. Merge sort is a recursive algorithm that continuously
splits the array in half until it cannot be further divided i.e., the array has only one
element left (an array with one element is always sorted). Then the sorted subarrays are
merged into one sorted array.

Working Principle:
1. Divide: Divide the unsorted list into n sublists, each containing one element. This
is the base case for the recursive algorithm.
2. Conquer: Recursively sort each sublist. If the sublist has more than one element,
apply the Merge Sort algorithm to it.
3. Merge: Merge the sorted sublists to produce new sorted sublists until there is only
one sublist remaining. This merging process involves comparing elements from
the two sublists and arranging them in the correct order.

• Worst Case Example

Here is a step-by-step explanation of the merge sort algorithm:
o If the array has only one element, it is already sorted.
o If the array has more than one element, we split it into two halves.
o We recursively apply the merge sort algorithm to each half.
o We merge the two sorted halves into a single sorted array.

Lets consider array [15,12,10,9,5,1]

15 12 10 9 5 1

Initially divide the array into two equal halves:

15 12 10 9 5 1

15 12 10 9 5 1
 Department of Computer Engineering
These subarrays are further divided into two halves until they become array of unit
length that can no longer be divided and array of unit length are always sorted

15 12 10 9 5 1

15 12 10 9 5 1

15 12 10 9 5 1

15 12 10 9 5 1

Merge the unit length subarrays into sorted subarrays

15 12 10 9 5 1

15 12 10 9 5 1

15 12 10 9 5 1

15 12 9 5 1
10

10 9 1 5
15 12

10 12 15 1 5 9

1 5 9 10 12 15
 Department of Computer Engineering
• Best Case Example
Here is a step-by-step explanation of the merge sort algorithm:
o If the array has only one element, it is already sorted.
o If the array has more than one element, we split it into two halves.
o We recursively apply the merge sort algorithm to each half.
o We merge the two sorted halves into a single sorted array.

Lets consider array [1,5,9,10,12,15]

1 5 9 10 12 15

Initially divide the array into two equal halves:

1 5 9 10 12 15

1 5 9 10 12 15

These subarrays are further divided into two halves until they become array of unit
length that can no longer be divided and array of unit length are always sorted

1 5 9 10 12 15

1 5 9 10 12 15

1 5 9 10 12 15

1 5 9 10 12 15

Merge the unit length subarrays into sorted subarrays

 Department of Computer Engineering
1 5 9 10 12 15

1 5 9 10 12 15

1 5 9 10 12 15

1 5 10 12 15
9

5 10 12 15
1 9

1 5 9 10 12 15

1 5 9 10 12 15
 Department of Computer Engineering
Algorithm:
Step 1. Divide: If the array has more than one element, find the middle index.
Step 2. Divide (Recursion): Recursively apply the merge sort algorithm to the left
and right halves of the array.
Step 3. Merge: Merge the sorted left and right halves back into a single sorted array.
a. Initialize three indices: i for the left half, j for the right half, and k
for the merged array.
b. Compare elements at indices i and j, and place the smaller one in the
merged array.
c. Move the index k and the index from which the element was taken.
d. Repeat until one of the halves is exhausted.
Step 4. Return the sorted array.

• Condition Merge sort will exhibit Best case, Worst case, Average case and what
is its best case, worst case, average case time.

1. Time complexity:
a. Best: The best-case scenario for merge sort occurs when the input array
is already sorted. In this case, the algorithm still divides the array into
two halves recursively, but it does not need to perform any comparisons
or swaps during the merge step. The time complexity of this process is
still O(n log n).
b. Worst: The worst-case scenario for merge sort occurs when the input
array is in reverse order. In this case, the algorithm still divides the array
into two halves recursively, but it needs to perform a large number of
comparisons and swaps during the merge step. The time complexity of
this process is still O(n log n).
c. Average: The average case scenario for merge sort occurs when the
input array is in random order. In this case, the algorithm still divides
the array into two halves recursively, but it needs to perform a average
number of comparisons and swaps during the merge step. The time
complexity of this process is still O(n log n).

2. Space complexity:
The space complexity of merge sort is O(n). This is because the algorithm
requires additional space to hold the merged halves of the array and In the
worst-case scenario, this requires storing an additional copy of the input array.
 Department of Computer Engineering
Source Code:
Program
#include <stdio.h>

void merge(int a[], int left[], int right[], int ls, int rs){
int i = 0, l = 0, r = 0;

while(l < ls && r < rs){

if(left[l] < right[r])
a[i++] = left[l++];
else
a[i++] = right[r++];
}

while(l < ls)

a[i++] = left[l++];
while(r < rs)
a[i++] = right[r++];
}

void mergeSort(int a[], int n){

if(n > 1){
int mid = n/2;
int left[mid], right[n-mid];
for(int i = 0, j = 0; i < n; i++){
if(i < mid)
left[i] = a[i];
else
right[j++] = a[i];
}
mergeSort(left, mid);
mergeSort(right, n-mid);
merge(a, left, right, mid, n-mid);
}
}

void printarr(int a[], int n) {

for (int i = 0; i < n; i++)
printf("%d ", a[i]);
printf("\n");
}
 Department of Computer Engineering
int main(){
int n;
printf("Enter the number of elements: ");
scanf("%d", &n);
int a[n];
printf("Enter the elements: ");
for(int i = 0; i < n; i++)
scanf("%d", &a[i]);

mergeSort(a, n);
printf("Sorted array: \n");
printarr(a, n);

return 0;
}
 Department of Computer Engineering
Output:
a) Random input:

b) Input sorted in ascending order:

c) Descending sorted input:

 Department of Computer Engineering
Conclusion:
From this algorithm we have concluded that merge sort is the most efficient algorithm for
sorting data and it is stable but not in-place. Although its space complexity is O(n), the time
complexity for best, worst and average case is same that is, O(nlogn).

Since the algorithm divides the array of data in two equal parts in each recursion call,
We can say it has taken ‘T(n/2)’ time for each half and ‘n’ time to merge all the divided
elements,

Therefore,
T(n) = 2T(n/2) + n

Now solving it by master’s theorem,

We have,
k = 1, a = 2, b = 2
therefore, 𝑙𝑜𝑔𝑏 𝑎 = 1

here k = 𝑙𝑜𝑔𝑏 𝑎

therefore, we can say that,

T(n) = O(nlogn)