Scribd
Upload
2 views3 pages

Merge Sort

The document provides a C/C++ program that implements the Merge Sort algorithm to sort a set of n integer elements and measures its time complexity. It generates random integers for sorting and records the time taken for various values of n greater than 5000. The program outputs the time taken for sorting and is intended to be used for plotting a graph of time versus n.

Uploaded by

remogowda9343
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
2 views3 pages

Merge Sort

The document provides a C/C++ program that implements the Merge Sort algorithm to sort a set of n integer elements and measures its time complexity. It generates random integers for sorting and records the time taken for various values of n greater than 5000. The program outputs the time taken for sorting and is intended to be used for plotting a graph of time versus n.

Uploaded by

remogowda9343
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

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 [Link] 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>

// Function to merge two subarrays of arr[]


void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;

// Create temporary arrays


int L[n1], R[n2];

// Copy data to temporary arrays L[] and R[]


for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];

// Merge the temporary arrays back into arr[l..r]


i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}

// Copy the remaining elements of L[], if any


while (i < n1) {
arr[k] = L[i];
i++;
k++;
}

// Copy the remaining elements of R[], if any


while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}

// l is for left index and r is right index of the sub-array of arr to be sorted
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;

// Sort first and second halves


mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);

merge(arr, l, m, r);
}
}

// Function to generate an array of random integers


void genrandom(int arr[], int n) {
for (int i = 0; i < n; i++) {
arr[i] = rand() % 10000; // Random numbers between 0 and 9999

}
}

int main() {
srand(time(0)); // Seed for random number generator

for (int n = 5000; n <= 100000; n += 5000) {


int* arr = (int*)malloc(n * sizeof(int));

genrandom(arr, n);

clock_t start, end;


double cpu_time_used;
start = clock();
mergeSort(arr, 0, n - 1);
end = clock();

cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;


printf("Time taken to sort %d elements: %f seconds\n", n, cpu_time_used);

free(arr);
}

return 0;
}

You might also like