Merge Sort

Merge Sort is a popular and efficient comparison-based sorting algorithm. It is based on the Divide and Conquer strategy. The main idea is to:

1. Divide the array into two halves.
2. Sort each half recursively.
3. Merge the sorted halves to produce the final sorted array.

Merge Sort is particularly good for large datasets and when consistent performance is needed.

How Merge Sort Works?

• Divide: Keep splitting the array into halves until each part contains only one element. A single-element array is always considered sorted.
• Conquer (Sort): Recursively sort the smaller arrays. Since single elements are already sorted, we start merging them in sorted order.
• Combine (Merge): Take two sorted arrays and merge them into one sorted array by comparing the elements of both.

Example: Merge Sort

Sort the array given below using merge sort. arr[] = {38, 27, 43, 3, 9, 82, 10}

Step 1: Divide

Split the array recursively and Divide into two halves

{38, 27, 43} and {3, 9, 82, 10}

Further split

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

{3, 9, 82, 10} → {3}, {9}, {82}, {10}

Step 2: Merge

Now start merging them back

Merge {38} and {27} → {27, 38}

Merge {27, 38} and {43} → {27, 38, 43}

Merge {3} and {9} → {3, 9}

Merge {82} and {10} → {10, 82}

Merge {3, 9} and {10, 82} → {3, 9, 10, 82}

Step 3: Final Merge

Now merge the two major halves

{27, 38, 43} and {3, 9, 10, 82}

Compare and combine to get the final sorted array:

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

Example 2: Sort the array given below using merge sort.

[12 , 35 ,87, 26, 9, 28, 7]

When to Use Merge Sort?

When you need stable sorting.

For large datasets where consistent performance is needed.

When working with linked lists or external sorting (like sorting data from disk).

When worst-case performance matters (unlike Quick Sort which can degrade to O(n²)).

Time and Space Complexity

The running time of merge sort in the average case and the worst case can be given as O(nLogn).

Although merge sort has an optimal time complexity, it needs an additional space of O(n) for the temporary array TEMP.

Advantages of Merge Sort

Stable sort: Maintains the relative order of equal elements.

Consistent performance: Always runs in O(n log n), even in the worst case.

Efficient for large datasets.

Suitable for linked lists: Unlike Quick Sort, Merge Sort works efficiently on linked lists.

Disadvantages of Merge Sort

High space complexity: Requires extra space of O(n) for merging.

Not in-place: It creates temporary arrays, so it's less memory efficient.

Overkill for small arrays: Simple sorts (like insertion sort) may perform better on small data.

Algorithm for Merge Sort

Input: An array arr of size n

Output: Sorted array in ascending order

1. If n < 2, return (base case)
2. Divide the array into two halves:
   - mid = n / 2
   - left = arr[0..mid-1]
   - right = arr[mid..n-1]
3. Recursively sort left and right
4. Merge the two sorted halves

C Program for Merge Sort

#include <stdio.h>

void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    // Temporary arrays
    int L[n1], R[n2];

    // Copy data to temp arrays
    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 temp arrays
    i = 0; j = 0; k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }

    // Copy remaining elements
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;

        // Sort first and second halves
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        merge(arr, l, m, r);
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array:\n");
    printArray(arr, n);

    mergeSort(arr, 0, n - 1);

    printf("Sorted array:\n");
    printArray(arr, n);

    return 0;
}

Output

Original array:
38 27 43 3 9 82 10 
Sorted array:
3 9 10 27 38 43 82 

Numerical Questions for Merge Sort

1. Sort the following array using Merge Sort and show all steps: {14, 7, 3, 12, 9, 11, 6, 2}

2. Sort this array using Merge Sort {25, 17, 31, 13, 2}

3. Perform Merge Sort on the following list and write the final sorted array {42, 29, 74, 11, 65, 58}

4. Sort the array using Merge Sort {90, 10, 30, 70, 20, 40, 60, 50}

5. Sort using Merge Sort and explain how the array becomes sorted from a descending order to ascending. {100, 85, 70, 55, 40, 25, 10}