Implement Quick sort and Merge sort and observe the execution time for various input sizes (Average, Worst and Best cases).

 #include <stdio.h>

#include <stdlib.h>

#include <time.h>

// ---------------- Quick Sort ----------------

int partition(int arr[], int low, int high) {

    int pivot = arr[high]; // last element as pivot

    int i = (low - 1), temp;

    for (int j = low; j < high; j++) {

        if (arr[j] <= pivot) {

            i++;

            temp = arr[i], arr[i] = arr[j], arr[j] = temp;

        }

    }

    temp = arr[i + 1], arr[i + 1] = arr[high], arr[high] = temp;

    return i + 1;

}

void quickSort(int arr[], int low, int high) {

    if (low < high) {

        int pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);

        quickSort(arr, pi + 1, high);

    }

}

// ---------------- Merge Sort ----------------

void merge(int arr[], int l, int m, int r) {

    int i, j, k;

    int n1 = m - l + 1, n2 = r - m;

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

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

    for (i = 0; i < n1; i++) L[i] = arr[l + i];

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

    i = j = 0, k = l;

    while (i < n1 && j < n2) arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];

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

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

    free(L); free(R);

}

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

    }

}

// ---------------- Helpers ----------------

void fillAscending(int arr[], int n) {

    for (int i = 0; i < n; i++) arr[i] = i;

}

void fillDescending(int arr[], int n) {

    for (int i = 0; i < n; i++) arr[i] = n - i;

}

void fillRandom(int arr[], int n) {

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

}

void copyArray(int* dest, int* src, int n) {

    for (int i = 0; i < n; i++) dest[i] = src[i];

}

void testSorts(int n) {

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

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

    clock_t start, end;

    double timeQS, timeMS;

    printf("\nArray size: %d\n", n);

    // --- Best Case (ascending for MergeSort)

    fillAscending(base, n);

    copyArray(arr, base, n);

    start = clock();

    quickSort(arr, 0, n - 1);

    end = clock();

    timeQS = ((double)(end - start)) / CLOCKS_PER_SEC * 1000000;

    copyArray(arr, base, n);

    start = clock();

    mergeSort(arr, 0, n - 1);

    end = clock();

    timeMS = ((double)(end - start)) / CLOCKS_PER_SEC * 1000000;

    printf("Best Case: QuickSort = %.2f µs, MergeSort = %.2f µs\n", timeQS, timeMS);

    // --- Worst Case (descending for QuickSort)

    fillDescending(base, n);

    copyArray(arr, base, n);

    start = clock();

    quickSort(arr, 0, n - 1);

    end = clock();

    timeQS = ((double)(end - start)) / CLOCKS_PER_SEC * 1000000;

    copyArray(arr, base, n);

    start = clock();

    mergeSort(arr, 0, n - 1);

    end = clock();

    timeMS = ((double)(end - start)) / CLOCKS_PER_SEC * 1000000;

    printf("Worst Case: QuickSort = %.2f µs, MergeSort = %.2f µs\n", timeQS, timeMS);

    // --- Average Case (random)

    fillRandom(base, n);

    copyArray(arr, base, n);

    start = clock();

    quickSort(arr, 0, n - 1);

    end = clock();

    timeQS = ((double)(end - start)) / CLOCKS_PER_SEC * 1000000;

    copyArray(arr, base, n);

    start = clock();

    mergeSort(arr, 0, n - 1);

    end = clock();

    timeMS = ((double)(end - start)) / CLOCKS_PER_SEC * 1000000;

    printf("Average Case: QuickSort = %.2f µs, MergeSort = %.2f µs\n", timeQS, timeMS);

    free(base); free(arr);

}

// ---------------- Main ----------------

int main() {

    srand(time(0));

    testSorts(1000);

    testSorts(5000);

    testSorts(10000);

    return 0;

}

Output: