Merge Sort Algorithm With Example Program

Introduction to Merge Sort

Merge Sort is a highly efficient sorting algorithm that follows the Divide and Conquer paradigm. It systematically divides the unsorted list into smaller sublists until each contains a single element. Then, these sublists are merged back together in a sorted manner, ultimately producing a fully sorted array.

Key Features of Merge Sort:

• Time Complexity: O(n log n) in the worst, average, and best cases.
• Stable Sort: Equal elements retain their original order.
• Efficient for Large Datasets: Due to its O(n log n) complexity, it is preferred for large datasets.
• Uses Extra Space: Requires additional space for merging operations.

How Merge Sort Works

Merge Sort recursively splits the array into two halves, sorts each half, and then merges them in a sorted manner.

Steps of Merge Sort:

1. Divide: Recursively split the array into halves until each subarray contains a single element.
2. Conquer: Sort and merge each subarray in a structured manner.
3. Combine: Merge the sorted subarrays to get the final sorted array.

Example of Merge Sort Algorithm

Let's consider an array: a[5] = {32, 40, 68, 3, 8}

The following C program demonstrates the implementation of Merge Sort:

#include <stdio.h>
#include <math.h>

void merge(int a[], int p, int q, int r) {
    int b[5]; // Temporary array
    int i = p, j = q + 1, k = 0;
    
    while (i <= q && j <= r) {
        if (a[i] < a[j]) {
            b[k++] = a[i++];
        } else {
            b[k++] = a[j++];
        }
    }
    while (i <= q) {
        b[k++] = a[i++];
    }
    while (j <= r) {
        b[k++] = a[j++];
    }
    for (i = r; i >= p; i--) {
        a[i] = b[--k];
    }
}

void mergesort(int a[], int p, int r) {
    if (p < r) {
        int q = floor((p + r) / 2);
        mergesort(a, p, q);
        mergesort(a, q + 1, r);
        merge(a, p, q, r);
    }
}

int main() {
    int a[] = {32, 40, 68, 3, 8};
    int n = sizeof(a) / sizeof(a[0]);
    
    mergesort(a, 0, n - 1);
    
    printf("Sorted Array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    return 0;
}

Explanation of the Code:

1. Merge Function: Merges two sorted halves into a sorted array.
2. Mergesort Function: Recursively splits the array and calls the merge function.
3. Main Function: Initializes the array, calls the mergesort() function, and prints the sorted output.

Output:

Sorted Array: 3 8 32 40 68

Conclusion

Merge Sort is an efficient and stable sorting algorithm suitable for large datasets. Unlike quicksort, it guarantees an O(n log n) time complexity in the worst case. While it requires extra space, its stability and efficiency make it an excellent choice for sorting applications.

Stay Connected!

This article is contributed by Developer Indian Team. If you found this article useful, feel free to follow us on:

• Instagram
• LinkedIn
• Facebook
• Twitter

For more articles and tutorials, keep following Developer Indian!