ADA Program 11

 

11. Merge Sort

/*Merge sort*/

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

void merge(int a[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int *L = (int*)malloc(n1 * sizeof(int));
    int *R = (int*)malloc(n2 * sizeof(int));

    for (int i = 0; i < n1; i++)
        L[i] = a[left + i];

    for (int j = 0; j < n2; j++)
        R[j] = a[mid + 1 + j];

    int i = 0, j = 0, k = left;

    while (i < n1 && j < n2) {
        if (L[i] <= R[j])
            a[k++] = L[i++];
        else
            a[k++] = R[j++];
    }

    while (i < n1) a[k++] = L[i++];
    while (j < n2) a[k++] = R[j++];

    free(L);
    free(R);
}

void mergeSort(int a[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(a, left, mid);
        mergeSort(a, mid + 1, right);
        merge(a, left, mid, right);
    }
}

int main() {
    int n, i;
    clock_t start, end;
    double time_taken;

    srand(time(NULL));

    FILE *fp = fopen("data.txt", "w");

    for (n = 5000; n <= 30000; n += 5000) {
        int *arr = (int *)malloc(n * sizeof(int));

        for (i = 0; i < n; i++)
            arr[i] = rand() % 100000;

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

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

        printf("N = %d, Time = %lf seconds\n", n, time_taken);
        fprintf(fp, "%d %lf\n", n, time_taken);

        free(arr);
    }

    fclose(fp);
    return 0;
}