Merge Sort in C: A Step-by-Step Guide with Code Examples

Merge Sort is a sorting algorithm that organizes data by comparing and merging elements. It ensures that items with the same value stay in their original order, making it a stable sorting method. The algorithm works by repeatedly dividing the list into smaller parts, sorting them individually, and then merging them back together in the correct order. 

However, it requires extra memory (O(n) space) to store and combine the divided sections, which can be a drawback compared to some other sorting techniques. Instead of this, Merge Sort in C is highly efficient for large datasets as it consistently performs well with a time complexity of O(n log n).

How Does Divide and Conquer Work?

The divide-and-conquer approach is a problem-solving technique that splits a complex problem into smaller, more manageable parts. Merge Sort is a classic example of the divide and conquer strategy. Here's how it works:

• Divide: The given array is split into two equal (or nearly equal) halves.
• Conquer: Each half is sorted separately using recursion.
• Combine: The sorted halves are merged to form a single, fully sorted array.

Merge Sort Algorithm In C

1. Check the array size: If the array has only one element or is empty, it's already sorted, so no further action is needed.
2. Find the middle point: Select the middle index to divide the array into two halves.
3. Sort each half recursively: Apply the Merge Sort algorithm separately to the left and right halves until each sub-array contains just one element.
4. Merge the sorted halves: Compare elements from both halves and combine them in the correct order to form a fully sorted array.

Note: This process continues until all elements are merged back together in sorted order. The merge sort algorithm in C follows a divide-and-conquer approach, breaking down the problem into smaller parts before combining the results.

Merge Sort in C is a divide-and-conquer algorithm that efficiently sorts an array by repeatedly splitting it into smaller sections and then merging them in sorted order. This approach provides stability and optimal time complexity. Here is a step-by-step breakdown of how it works:

Step 1: Splitting the Array into Two Parts

The merge sort algorithm in C begins by splitting the given array into two equal (or nearly equal) halves.

Step 2: Recursively Dividing the Subarrays

Each half is further split into smaller sections until we reach individual elements. For example, the left half is divided into two smaller arrays of size 2.

Step 3: Sorting and Merging Individual Elements

After reaching the smallest subarrays, each element is sorted, and the merging process begins by combining them in sorted order.

Step 4: Merging the Two Sorted Halves

Finally, the two sorted halves of the array are merged into a single sorted array. This merging process ensures that the entire array is sorted correctly in ascending order, following the principles of the merge sort algorithm in C for efficient and reliable sorting.

Recurrence Relation of Merge Sort

The time complexity of Merge Sort can be understood using a mathematical formula that explains how the algorithm performs as the input size increases. This formula is based on the divide-and-conquer method used in Merge Sort. It can be written as:

Here is the flowchart representation of Merge Sort in C, visually showing how the algorithm processes an array step-by-step.

                [Unsorted Array]
                      |
          ----------------------
          |                    |
     [Left Half]          [Right Half]
          |                     |
   --------------        --------------
   |            |        |            |
[Smaller]  [Smaller]   [Smaller]  [Smaller]
          |                      |
     [Sorted Left]       [Sorted Right]
          \                /
          [Merged Sorted Array]

1. Recursive Approach

Merge Sort is a divide-and-conquer sorting algorithm that splits an array into smaller parts, sorts them, and then merges them back in order. The recursive function divides the array into two halves, sorts them separately, and then merges them efficiently. Here is the merge sort C code detailed explanation:

Merge Sort C Code:

#include <stdio.h>

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

    for (int i = 0; i < n1; i++)
        leftArr[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        rightArr[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k++] = leftArr[i++];
        } else {
            arr[k++] = rightArr[j++];
        }
    }

    while (i < n1) {
        arr[k++] = leftArr[i++];
    }
    while (j < n2) {
        arr[k++] = rightArr[j++];
    }
}

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

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

int main() {
    int arr[] = {70, 50, 30, 10, 20, 40, 60};
    int size = sizeof(arr) / sizeof(arr[0]);

    printf("Original array:\n");
    printArray(arr, size);
    
    mergeSort(arr, 0, size - 1);
    
    printf("\nSorted array:\n");
    printArray(arr, size);
    return 0;
}

Explanation

Merge Sort in C works by dividing an array into two halves, sorting them recursively, and merging them back in order. The merge() function merges two sorted halves, while mergeSort() handles recursive splitting. This ensures that elements are compared and placed correctly.

Output

Original array:
70 50 30 10 20 40 60 

Sorted array:
10 20 30 40 50 60 70

Time and Space Complexity:

• Time Complexity: O(n log n) in all cases (best, average, worst).
• Space Complexity: O(n) due to the temporary arrays used for merging.

2. Iterative Merge Sort C Implementation

Unlike the recursive version, the merge sort algorithm in C follows an iterative approach that sorts the array in a bottom-up manner. It begins with small subarrays of size 1, merges them into sorted subarrays of size 2, then 4, and continues this process until the entire array is sorted.  Here is the merge sort C code detailed explanation:

Merge Sort C Code:

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

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

    for (int i = 0; i < n1; i++)
        leftArr[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        rightArr[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k++] = leftArr[i++];
        } else {
            arr[k++] = rightArr[j++];
        }
    }

    while (i < n1) {
        arr[k++] = leftArr[i++];
    }
    while (j < n2) {
        arr[k++] = rightArr[j++];
    }
}

void iterativeMergeSort(int arr[], int n) {
    int curr_size, left_start;

    for (curr_size = 1; curr_size < n; curr_size *= 2) {
        for (left_start = 0; left_start < n - 1; left_start += 2 * curr_size) {
            int mid = left_start + curr_size - 1;
            int right_end = (left_start + 2 * curr_size - 1 < n - 1) ?
                            (left_start + 2 * curr_size - 1) : (n - 1);
            merge(arr, left_start, mid, right_end);
        }
    }
}

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

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

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

    iterativeMergeSort(arr, n);

    printf("\nSorted array:\n");
    printArray(arr, n);
    return 0;
}

Explanation

This version of Merge Sort C Code processes the array iteratively, merging pairs of subarrays in increasing sizes (1, 2, 4, etc.) until the entire array is sorted. It avoids recursion, making it more memory-efficient.

Output

Original array:
12 11 13 5 6 7 

Sorted array:
5 6 7 11 12 13 

Time and Space Complexity:

• Time Complexity: O(n log n) in all cases (best, average, worst).
• Space Complexity: O(n) due to temporary arrays used for merging.

1. Sorting Linked Lists

The merge sort algorithm in C is ideal for sorting linked lists because it efficiently handles sequential data access. Unlike array-based sorting algorithms, it doesn’t require random element access, making it well-suited for linked structures. It maintains order without excessive memory movement by repeatedly dividing and merging nodes, ensuring stable and efficient sorting.

2. Handling Large Datasets

Merge Sort in C is useful when sorting large datasets that don’t fit into a computer’s RAM. It processes data in smaller chunks, sorts them individually, and merges them back together efficiently. This makes it valuable for external storage systems like databases and file management applications.

3. Counting Inversions in Data Analysis

Merge Sort helps count inversions, which is useful in fields like finance and computational biology. In finance, it analyzes stock trends by measuring how far a dataset is from being sorted. In genetics, it helps compare DNA sequences by identifying differences and mutations.

1. Maintains Order of Equal Elements: Merge Sort in C is a stable algorithm, meaning it preserves the original order of elements that have the same value.
2. Reliable Performance: It consistently operates in O(n log n) time complexity, regardless of the input, ensuring efficiency even for large datasets.
3. Works Well with Parallel Processing: Since Merge Sort divides the array into independent subarrays, it can be effectively parallelized in multi-threaded environments.
4. Handles Large Data Efficiently: Merge Sort is especially useful when working with large datasets stored in external memory, like hard drives, due to its predictable access patterns.‍
5. Suitable for Linked Lists: Unlike some sorting algorithms, Merge Sort works very well with linked lists, making it versatile for different data structures.

1. High Memory Usage: Requires O(n) auxiliary space, making it less suitable for memory-constrained environments.
2. Inefficient for Small Arrays: The overhead from recursive function calls and combining operations in the merge sort algorithm in C can make it slower than simpler sorting algorithms like Insertion Sort for small n.
3. Not In-Place: Merge Sort does not sort the elements in place, as it relies on additional memory to store temporary subarrays during the merging process.
4. Complex Implementation: Compared to simpler sorting algorithms like Bubble or Selection Sort, Merge Sort has a more complex implementation that may be harder for beginners to grasp.‍
5. Slower on Certain Inputs: For datasets that are already nearly sorted or small in size, Merge Sort may perform worse than algorithms like Insertion Sort, which are optimized for such cases.

Merge Sort in C has a divide-and-conquer approach that provides efficient sorting with optimal time complexity, making it indispensable for large-scale data processing. While its space complexity is a drawback, its stability and predictability often outweigh this limitation. Mastery of Merge Sort is crucial for tackling advanced algorithmic challenges in competitive programming and real-world applications.

1. How does Merge Sort work in C?

The array is repeatedly divided into two halves until each part has only one element. Then, these smaller parts are merged while sorting them, resulting in a fully sorted array.

2. What is the time complexity of Merge Sort?

Merge Sort runs in O(n log n) time for all cases (best, average, and worst), making it efficient for sorting large datasets.

3. What are the advantages of Merge Sort?

It maintains stability (keeps equal elements in order), works well with linked lists, and always sorts in O(n log n) time, no matter the input order.

4. What are the disadvantages of Merge Sort in C?

It needs extra memory space O(n) for merging subarrays and can be slower for small datasets due to the overhead of recursive function calls.

5. Where is Merge Sort used in real-world applications?

Merge Sort is used in external sorting (handling huge datasets), sorting linked lists, and solving problems like counting inversions in competitive programming.

6. Can Merge Sort be implemented iteratively in C?

Yes, instead of recursion, an iterative version can use loops to handle subarrays and merge them step by step.