C:\Users\jayap\Desktop\2025-2025-Even Semester\BCS401-Analysis and Design of Algorithms\404 Lab Programs\11 Prg\merge_sort - Copy.
c Friday, 18 April, 2025 10:48 AM
/* 11. Design and implement C/C++ Program to sort a given set of
n integer elements using Merge Sort method and compute its time
complexity. Run the program for varied values of n> 5000, and record
the time taken to sort. Plot a graph of the time taken versus n.
The elements can be read from a file or can be generated using
the random number generator.
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_SIZE 100000
// Merge function
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[50000], R[50000]; // Avoid pointers
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
-1-
C:\Users\jayap\Desktop\2025-2025-Even Semester\BCS401-Analysis and Design of Algorithms\404 Lab Programs\11 Prg\merge_sort - Copy.c Friday, 18 April, 2025 10:48 AM
i = 0; j = 0; k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j]) arr[k++] = L[i++];
else arr[k++] = R[j++];
}
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
// Merge Sort function
void mergeSort(int arr[], int l, int r)
{
if (l < r)
{
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
// Main function
-2-
C:\Users\jayap\Desktop\2025-2025-Even Semester\BCS401-Analysis and Design of Algorithms\404 Lab Programs\11 Prg\merge_sort - Copy.c Friday, 18 April, 2025 10:48 AM
int main()
{
int arr[MAX_SIZE];
int n;
FILE *fp = fopen("merge_sort_results.txt", "w");
fprintf(fp, "n,time(ms)\n");
printf("Running Merge Sort for different values of n (n >
5000)...\n");
for (n = 5000; n <= 50000; n += 5000)
{
// Generate random numbers
for (int i = 0; i < n; i++)
{
arr[i] = rand() % 100000;
}
clock_t start = clock();
mergeSort(arr, 0, n - 1);
clock_t end = clock();
double time_taken = ((double)(end - start)) * 1000.0 /
CLOCKS_PER_SEC;
printf("n = %d \t Time = %.3f ms\n", n, time_taken);
-3-
C:\Users\jayap\Desktop\2025-2025-Even Semester\BCS401-Analysis and Design of Algorithms\404 Lab Programs\11 Prg\merge_sort - Copy.c Friday, 18 April, 2025 10:48 AM
fprintf(fp, "%d\t%.3f\n", n, time_taken);
}
fclose(fp);
printf("\nResults saved in 'merge_sort_results.txt'.\n");
return 0;
}
/* OUTPUT
merge_sort_results.txt
n,time(ms)
5000 4.000
10000 5.000
15000 13.000
20000 13.000
25000 12.000
30000 13.000
35000 17.000
40000 24.000
45000 23.000
50000 41.000
*/
# Python Code to Plot Graph
-4-
C:\Users\jayap\Desktop\2025-2025-Even Semester\BCS401-Analysis and Design of Algorithms\404 Lab Programs\11 Prg\merge_sort - Copy.c Friday, 18 April, 2025 10:48 AM
import [Link] as plt
# Read data from the file
def read_data(filename):
with open(filename, 'r') as file:
lines = [Link]()[1:] # Skip the header
n_values, time_values = [], []
for line in lines:
n, time = map(float, [Link]())
n_values.append(int(n))
time_values.append(time)
return n_values, time_values
# Plot the data
def plot_graph(n_values, time_values):
[Link](figsize=(8, 5))
[Link](n_values, time_values, marker='o', linestyle='-', color=
'b', label='Time vs n')
[Link]('n (Number of elements)')
[Link]('Time taken (seconds)')
[Link]('Time Complexity of Merge Sort')
[Link]()
[Link](True)
[Link]()
-5-
C:\Users\jayap\Desktop\2025-2025-Even Semester\BCS401-Analysis and Design of Algorithms\404 Lab Programs\11 Prg\merge_sort - Copy.c Friday, 18 April, 2025 10:48 AM
# Main execution
filename = "C:/Users/jayap/Desktop/2025-2025-Even
Semester/BCS401-Analysis and Design of Algorithms/404 Lab Programs/11
Prg/merge_sort_results.txt"
n_values, time_values = read_data(filename)
plot_graph(n_values, time_values)
OUTPUT :
-6-
