Merge Sort Algorithm in C, C++, Java with Examples

Introduction

Sorting algorithms are essential in computer science, and Merge Sort stands out due to its efficiency. Unlike Bubble Sort, Selection Sort, or Insertion Sort, Merge Sort follows the Divide and Conquer approach, ensuring better performance for large datasets. In this article, we will explore the Merge Sort algorithm, its working mechanism, and implementations in C, C++, and Java.

What is Merge Sort?

Merge Sort is a recursive sorting algorithm that divides an array into two halves, sorts them individually, and then merges the sorted halves. This method ensures a stable sorting mechanism with a time complexity of O(n log n) in all cases.

Key Features of Merge Sort:

• Uses the Divide and Conquer paradigm.
• Works efficiently for large datasets.
• Requires additional space for merging, making it not an in-place sorting algorithm.

How Merge Sort Works

1. Divide: The array is split into two halves recursively until each subarray contains a single element.
2. Conquer: Each half is sorted recursively.
3. Merge: The sorted halves are merged back to form a single sorted array.

Visualization of Merge Sort:

A step-by-step breakdown for an example array [4, 8, 13, 2, 23, 16]:

Original Array: [4, 8, 13, 2, 23, 16]
Step 1: Divide into [4, 8, 13] and [2, 23, 16]
Step 2: Further divide into [4], [8, 13], [2], [23, 16]
Step 3: Further divide until single elements remain
Step 4: Merge sorted subarrays: [4, 8, 13] and [2, 16, 23]
Step 5: Final Merge: [2, 4, 8, 13, 16, 23]

Merge Sort Algorithm (Pseudocode)

MERGE-SORT(arr, start, end)
  if start < end
    mid = (start + end) / 2
    MERGE-SORT(arr, start, mid)
    MERGE-SORT(arr, mid + 1, end)
    MERGE(arr, start, mid, end)

MERGE(arr, start, mid, end)
  Create two temporary arrays left[] and right[]
  Copy elements to left[] and right[]
  Merge the two arrays in sorted order back into arr[]

Merge Sort Implementation in C, C++, and Java

Merge Sort in C

#include <stdio.h>
void merge(int arr[], int left, int mid, int right) {
    int i, j, k;
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int L[n1], R[n2];
    for (i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];
    i = 0; j = 0; k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[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);
    }
}

Merge Sort in C++

#include <iostream>
using namespace std;
void merge(int arr[], int left, int mid, int right) {
    int i, j, k;
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int L[n1], R[n2];
    for (i = 0; i < n1; i++) L[i] = arr[left + i];
    for (j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];
    i = 0; j = 0; k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[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);
    }
}

Merge Sort in Java

class MergeSort {
    void merge(int arr[], int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;
        int L[] = new int[n1];
        int R[] = new int[n2];
        for (int i = 0; i < n1; i++)
            L[i] = arr[left + i];
        for (int j = 0; j < n2; j++)
            R[j] = arr[mid + 1 + j];
        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) arr[k++] = L[i++];
            else arr[k++] = R[j++];
        }
        while (i < n1) arr[k++] = L[i++];
        while (j < n2) arr[k++] = R[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);
        }
    }
}

Time Complexity of Merge Sort

Conclusion

Merge Sort is one of the most efficient sorting algorithms for large datasets due to its O(n log n) complexity. While it requires extra memory, its stable sorting and predictable time complexity make it a preferred choice for many applications.