lab11

 #include <stdio.h> 

#include <stdlib.h> 

#include <time.h> 

// Merge two subarrays of arr[]. 

// First subarray is arr[l..m] 

// Second subarray is arr[m+1..r] 

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; 

j = 0; 

k = l; 

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++; 

} 

36 

Department of CSE (CY), RNSIT         

IV Semester          BCSL404 – ADA LABORATORY 

 

Department of CSE (CY), RNSIT         37 

 

 

 

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

    while (j < n2) { 

        arr[k] = R[j]; 

        j++; 

        k++; 

    } 

} 

 

// Merge Sort function 

void mergeSort(int arr[], int l, int r) { 

    if (l < r) { 

        // Same as (l+r)/2, but avoids overflow for large l and r 

        int m = l + (r - l) / 2; 

 

        // Sort first and second halves 

        mergeSort(arr, l, m); 

        mergeSort(arr, m + 1, r); 

 

        // Merge the sorted halves 

        merge(arr, l, m, r); 

    } 

} 

 

int main() { 

    int n, i; 

    clock_t start, end; 

    double cpu_time_used; 

 

    printf("Enter the number of elements (n): "); 

    scanf("%d", &n); 

 

    if (n < 5000) { 

        printf("Please enter a value of n greater than 5000.\n"); 

        return 1; 

    } 

 

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

    if (arr == NULL) { 

        printf("Memory allocation failed.\n"); 

        return 1; 

    } 

 

    // Generate n random numbers 

    srand(time(NULL)); 

    // printf("Randomly generated array: "); 

    for (i = 0; i < n; i++) { 

        arr[i] = rand() % 10000; // Generating random numbers between 0 to 

9999 

        // printf("%d ", arr[i]); 

IV Semester          BCSL404 – ADA LABORATORY 

 

Department of CSE (CY), RNSIT         38 

 

 

    } 

    // printf("\n"); 

 

    // Record the starting time 

    start = clock(); 

 

    // Perform Merge Sort 

    mergeSort(arr, 0, n - 1); 

 

    // Record the ending time 

    end = clock(); 

 

    // Calculate the time taken 

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

 

    // printf("Sorted array: "); 

    // for (i = 0; i < n; i++) { 

    //     printf("%d ", arr[i]); 

    // } 

    // printf("\n"); 

 

    printf("Time taken for sorting: %lf seconds\n", cpu_time_used); 

 

    free(arr); // Free dynamically allocated memory 

    return 0; 

}