Scribd
Upload
3 views5 pages

Program 2

The document outlines the process of the Merge Sort algorithm, detailing the steps of dividing an array into halves and merging sorted subarrays. It includes a C/C++ program that implements Merge Sort, measures its time complexity for varying sizes of input, and records the results. The program generates random integers to sort and outputs the time taken for sorting in milliseconds.

Uploaded by

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

Program 2

The document outlines the process of the Merge Sort algorithm, detailing the steps of dividing an array into halves and merging sorted subarrays. It includes a C/C++ program that implements Merge Sort, measures its time complexity for varying sizes of input, and records the results. The program generates random integers to sort and outputs the time taken for sorting in milliseconds.

Uploaded by

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

Step 1: Merge 3

[3] + [9] → [3, 9]


Divide the Merge 4
Array [82] + [10]
Compare:
10 < 82 → [10, 82]
Merge sort keeps Merge 5
dividing the array [3, 9] + [10, 82]
into two halves until → [3, 9, 10, 82]
each part has one
element. Right side becomes:

[38, 27, 43, 3, [3, 9, 10, 82]


9, 82, 10]

/
\ Final Merge
[38, 27, 43]
[3, 9, 82, 10]
[27, 38, 43] + [3, 9, 10, 82]
/ \ Compare elements step by step:
/ \
[38] [27, 3 → [3]
43] [3,
9] [82, 10]
9 → [3, 9]
10 → [3, 9, 10]
/ 27 → [3, 9, 10, 27]
\ / 38 → [3, 9, 10, 27, 38]
\ / \
[27] 43 → [3, 9, 10, 27, 38, 43]
[43] [3] 82 → [3, 9, 10, 27, 38, 43, 82]
[9] [82] [10]
[3, 9, 10, 27, 38, 43, 82]

Step 2: Divide → Divide → Divide → Merge → Merge → Sorted Array


Merge and lab program
Sort 1. Design and implement Program in C/C++ to sort a given set of n integer
elements using Merge sort method and compute its time complexity. Run
Now the algorithm
the program for varied values of n> 5000 and record the time taken to
merges sorted
subarrays. 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.
Merge 1
[27] + [43] →
[27, 43]
Merge 2
[38] + [27, 43]
Compare:
27 < 38 → [27]
38 < 43 → [27,
38]
Remaining → [27,
38, 43]

Left side becomes:

[27, 38, 43]


#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// Function to merge two halves


void merge(long int a[], int low, int mid, int high) {
int i = low, j = mid + 1, k = low;
long int b[100000]; // Temporary array

while (i <= mid && j <= high) {


if (a[i] <= a[j])
b[k++] = a[i++];
else
b[k++] = a[j++];
}

while (i <= mid)


b[k++] = a[i++];

while (j <= high)


b[k++] = a[j++];

for (i = low; i <= high; i++)


a[i] = b[i];
}

// Main mergeSort function


void mergeSort(long int a[], int low, int high) {
if (low < high) {
int mid = (low + high) / 2;
mergeSort(a, low, mid);
mergeSort(a, mid + 1, high);

merge(a, low, mid, high);


}
}

int main() {
long int n = 10000;
int it = 0;
double tim3[10];

srand(time(NULL));

printf("A_size, MergeSort Time\n");

while (it < 10) {

long int c[n];

// Generate random numbers


for (long int i = 0; i < n; i++) {
long int no = rand() % n + 1;
c[i] = no;
}

clock_t start, end;

start = clock();
mergeSort(c, 0, n - 1); // corrected array name
end = clock();

tim3[it] = ((double)(end - start)) / CLOCKS_PER_SEC * 10000;

printf("%li, %li ms\n", n, (long int)tim3[it]);

n += 10000;
it++;
}

return 0;
}
arr[k] = R[j]; j++;

You might also like