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

Merge sort splits an array in half, recurses on each half, and merges the sorted halves back together in O(n log n) time regardless of input order.

That guarantee makes it one of the few comparison-based sorts with no pathological worst case. The trade-off is O(n) auxiliary space. Below is everything you need: the divide-and-conquer logic, a traced walkthrough, complexity analysis, a head-to-head with quicksort, and compilable code in C, C++, and Java.

How Divide and Conquer Applies to Merge Sort

Divide and conquer breaks a problem into smaller sub-problems of the same type, solves each recursively, then combines the results. Merge sort applies this in three steps:

• Divide — find the midpoint and split the array into two halves.
• Conquer — recursively sort the left half and the right half.
• Combine — merge the two sorted halves into a single sorted array.

The recursion bottoms out when a sub-array has zero or one element (already sorted by definition). All the real work happens in the merge step, which walks both halves with two pointers and picks the smaller element at each position.

The algorithm was invented by John von Neumann in 1945, making it one of the oldest documented sorting methods still in production use.

Step-by-Step Walkthrough

Consider the array [38, 27, 43, 3, 9, 82, 10]. Here is the full recursion tree:

Splitting phase

• Level 0: [38, 27, 43, 3, 9, 82, 10]
• Level 1: [38, 27, 43] and [3, 9, 82, 10]
• Level 2: [38], [27, 43], [3, 9], [82, 10]
• Level 3: [38], [27], [43], [3], [9], [82], [10]

Merging phase

• Merge [27] + [43] → [27, 43]
• Merge [38] + [27, 43] → [27, 38, 43]
• Merge [3] + [9] → [3, 9]
• Merge [82] + [10] → [10, 82]
• Merge [3, 9] + [10, 82] → [3, 9, 10, 82]
• Merge [27, 38, 43] + [3, 9, 10, 82] → [3, 9, 10, 27, 38, 43, 82]

Each merge pass does at most n comparisons across that level, and there are log2(7) ≈ 3 levels, giving roughly 7 × 3 = 21 comparison operations for this 7-element array.

Complexity Analysis

Case	Time Complexity	Reason
Best	O(n log n)	Still splits and merges every level even if input is sorted
Average	O(n log n)	Merge cost is linear at each of log n levels
Worst	O(n log n)	No input ordering degrades the recursion tree

• Space: O(n) auxiliary for the temporary arrays during merge.
• Recurrence: T(n) = 2T(n/2) + O(n). By the Master Theorem (case 2, where a = 2, b = 2, f(n) = O(n)), this resolves to O(n log n).
• Stable: Yes. The <= comparison in the merge loop preserves the relative order of equal elements.
• In-place: No. The merge step allocates temporary storage proportional to n.

Merge Sort vs Quicksort

Property	Merge Sort	Quicksort
Worst-case time	O(n log n)	O(n²) (rare with randomised pivot)
Average-case time	O(n log n)	O(n log n)
Space	O(n) auxiliary	O(log n) stack (in-place partition)
Stable	Yes	No (standard Lomuto/Hoare partition)
Cache performance	Poor (non-sequential writes to temp arrays)	Good (sequential in-place swaps)
Preferred when	Stability required, linked lists, external sorting	Arrays in RAM, average-case speed matters

In placement interviews, the follow-up to “implement merge sort” is often “why not quicksort?” The short answer: merge sort when you need guaranteed O(n log n) or stability; quicksort when you need speed on arrays that fit in memory and can tolerate O(n²) in rare cases.

Implementation in C, C++, and Java

All three implementations sort the array [38, 27, 43, 3, 9, 82, 10] and print the result [3, 9, 10, 27, 38, 43, 82].

C Implementation

#include <stdio.h>

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int L[n1], R[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);
    }
}

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

    mergeSort(arr, 0, n - 1);

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

Output: 3 9 10 27 38 43 82

C++ Implementation

#include <iostream>
#include <vector>
using namespace std;

void merge(vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    vector<int> L(n1), R(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(vector<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);
    }
}

int main() {
    vector<int> arr = {38, 27, 43, 3, 9, 82, 10};

    mergeSort(arr, 0, arr.size() - 1);

    for (int x : arr)
        cout << x << " ";
    cout << endl;
    return 0;
}

Output: 3 9 10 27 38 43 82

Java Implementation

public class MergeSort {

    static 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++];
    }

    static 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);
        }
    }

    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};

        mergeSort(arr, 0, arr.length - 1);

        for (int x : arr)
            System.out.print(x + " ");
        System.out.println();
    }
}

Output: 3 9 10 27 38 43 82

Key Points Across All Three

• mid = left + (right - left) / 2 prevents integer overflow on large arrays (compared to (left + right) / 2).
• The <= in the merge comparison ensures stability.
• The C version uses C99 variable-length arrays. The C++ version uses std::vector for standards compliance. The Java version uses new int[].

When to Use Merge Sort in Practice

Merge sort is the default choice in three scenarios:

• External sorting — when data doesn’t fit in RAM, merge sort’s sequential access pattern works well with disk I/O. Most database engines use a variant of merge sort for large joins.
• Linked lists — no random access means quicksort loses its cache advantage. Merge sort on linked lists needs O(log n) stack space and zero auxiliary arrays.
• Stability required — Java’s Arrays.sort() for objects uses TimSort, which is a hybrid of merge sort and insertion sort, precisely because stability is non-negotiable for object sorting.

For arrays that fit in memory where stability doesn’t matter, quicksort (or introsort, which falls back to heapsort on bad pivots) is typically faster by a constant factor due to cache locality.

If you’re preparing for data structures interview questions, merge sort is almost guaranteed to appear, either as a direct implementation question or as a building block for problems like “count inversions in an array” or “merge k sorted lists.” Understanding the merge step also helps with problems like finding the smallest and largest element in an array efficiently, and the recursive structure mirrors other divide-and-conquer problems like checking whether a string is a palindrome recursively.

Beyond Sorting: Where This Thinking Leads

The recurrence T(n) = 2T(n/2) + O(n) shows up everywhere in algorithm design, from closest-pair-of-points to FFT. Once you’ve internalised the merge-sort decomposition, you’ve internalised the template for an entire class of problems. TinkerLLM’s sandbox at ₹299 lets you prototype sorting visualisations, trace recursion trees with LLM-generated code, and build the kind of interactive DSA projects that stand out on a GitHub profile during placement season.