Program 10 : Merge Sort

Sort a given set of elements using Merge sort and determine the time required to sort n elements. Repeat the experiment for different values of n and plot a graph of the time taken versus n

Merge Sort

• For a given array, find the mid point,
• Sort the left to mid and mid+1 to right side recursively till left is greater than right(one element or zero)
• Start merging the two halves by comparing each.
• make two temporary copies of the left right array by getting there sizes.
• Compare each values in these two arrays and add that to the left of main array.
• continue till any one of the array becomes empty
• Put the rest of the elements in main array.
• Done

#include <stdio.h>

void merge(int arr[], int left, int mid, int right) {
    int n1 = (mid - left) + 1; // size of left sub array
    int n2 = right - mid;  // size of right sub array
    // Create temp arrays
    int L[n1], R[n2];

    // Copy data to temp arrays
	int i, j;
	
    for (i = 0; i < n1; i++)
        L[i] = arr[left + i];
        // from left upto mid, left has mid
        
    for (j = 0; j < n2; j++)
        R[j] = arr[mid + j + 1];
		// starts at mid+1
    
    // Merge the temp arrays back into arr[left..right]
    i = j = 0;
    int k = left; // start of actual array

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

    // Copy any remaining elements of L[]
    while (i < n1)
        arr[k++] = L[i++];

    // Copy any remaining elements of R[]
    while (j < n2)
        arr[k++] = R[j++];
}

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        // int mid = (left + right)/2 
        // works sam, may overflow

        // Sort first and second halves
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        // Merge the sorted halves
        merge(arr, left, mid, right);
    }
}

void displayArray(int arr[], int n) {
    printf("Sorted array:\n");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[100], n;

    printf("Enter number of elements: ");
    scanf("%d", &n);

    printf("Enter %d elements:\n", n);
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    mergeSort(arr, 0, n - 1);
    displayArray(arr, n);

    return 0;
}

---

Merge Sort

Merge Sort is a divide-and-conquer algorithm. It divides the array into smaller subarrays, sorts them, and then merges them back together.

Algorithm Steps:

1. Divide:

   • Split the array into two halves.

   • Repeat recursively until each subarray has one element (a single-element array is considered sorted).

2. Conquer:

   • Sort the two halves (this happens recursively).

3. Combine:

   • Merge the two sorted halves into one sorted array using a helper function.

Example:

Input: {38, 27, 43, 3, 9, 82, 10}

• Divide into {38, 27, 43} and {3, 9, 82, 10}

• Continue dividing:

  • {38, 27, 43} → {38}, {27, 43} → {27}, {43}

  • {3, 9, 82, 10} → {3, 9}, {82, 10} → etc.

• Merge:

  • {27, 43} → {27, 38, 43}, {3, 9} → {3, 9}, etc.

• Final merge → Sorted array

---

Time Complexity

Case	Time
Best	O(n log n)
Average	O(n log n)
Worst	O(n log n)

• Space Complexity: O(n) (due to use of temporary arrays)

• Stable: Yes

• In-place: No (requires extra space)

Simplified Version

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

void merge(int a[], int l, int m, int r) {
    int i = l, j = m + 1, k = 0;
    int *temp = malloc((r - l + 1) * sizeof(int));

    while (i <= m && j <= r)
        temp[k++] = (a[i] < a[j]) ? a[i++] : a[j++];

    while (i <= m)
        temp[k++] = a[i++];
    while (j <= r)
        temp[k++] = a[j++];

    for (i = l, k = 0; i <= r; i++, k++)
        a[i] = temp[k];

    free(temp);
}

void mergeSort(int a[], int l, int r) {
    if (l < r) {
        int m = (l + r) / 2;
        mergeSort(a, l, m);
        mergeSort(a, m + 1, r);
        merge(a, l, m, r);
    }
}

int main() {
    int a[100], n;
    printf("Enter number of elements: ");
    scanf("%d", &n);
    printf("Enter %d elements:\n", n);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    mergeSort(a, 0, n - 1);

    printf("Sorted array:\n");
    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);
    printf("\n");

    return 0;
}