MERGE SORT ALGORITHM IN C AND C++

Merge Sort in C++ (with detailed explanations)

This program implements the Merge Sort algorithm, one of the most well-known sorting algorithms based on the divide and conquer paradigm.

The algorithm works as follows:

• the array is recursively divided into two approximately equal parts,
• the left and right subarrays are sorted independently,
• the two sorted subarrays are then merged into a single sorted array.

mergeArrays function – merging two sorted subarrays

The function mergeArrays receives the following parameters:

• a[] – the original array,
• l – left index of the segment being merged,
• m – middle index (end of the left subarray),
• r – right index of the segment,
• n – total length of the array.

The goal is to merge two already sorted subarrays: [l ... m] and [m+1 ... r] into a single sorted segment.

#include <iostream>
using namespace std;

void mergeArrays(int a[], int l, int m, int r, int n)
{
    int k, i, j;

    // STEP 1: Create a temporary copy of the array
    // Note: the entire array is copied, which is not optimal
    int aCopy[n];
    for (int i = 0; i < n; i++)
    {
        aCopy[i] = a[i];
    }

    // STEP 2: Initialize indices
    // i -> left subarray
    // j -> right subarray
    // k -> position in the original array
    for (i = k = l, j = m + 1; i <= m && j <= r; k++)
    {
        // STEP 3: Compare elements from left and right subarrays
        if (aCopy[j] < aCopy[i])
        {
            a[k] = aCopy[j];
            j++;
        }
        else
        {
            a[k] = aCopy[i];
            i++;
        }
    }

    // STEP 4: Copy remaining elements from the left subarray
    for (; i <= m; i++, k++)
    {
        a[k] = aCopy[i];
    }

    // Remaining elements from the right subarray
    // are already in correct positions
}

Important note: This implementation is correct but inefficient because it copies the entire array into a temporary buffer, even though only the segment [l ... r] needs to be merged.

mergeSort function – recursive array division

The mergeSort function recursively divides the array until each subarray contains only one element, which is trivially sorted.

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

        // Sort the left half
        mergeSort(a, l, m, n);

        // Sort the right half
        mergeSort(a, m + 1, r, n);

        // Merge the sorted halves
        mergeArrays(a, l, m, r, n);
    }
}

The recursion stops when l == r, because a segment with a single element is already sorted.

Time and space complexity

• Time complexity:O(n log n) in the best, average, and worst case.
• Space complexity:O(n) due to the use of an auxiliary array.

Because of its stable time complexity, Merge Sort is well suited for large datasets, but it requires additional memory.

Where this code can be improved

• The parameter n should not be passed through every recursive call.
• The auxiliary array should not be created inside each merge operation.
• Only the segment [l ... r] should be copied, not the entire array.

Guidelines for a more optimal implementation

A more efficient approach is to:

• create a single auxiliary array with the same size as the original array,
• pass it through recursive calls,
• copy only the portion of the array that is currently being merged.

// Conceptual outline of an optimized approach
void merge(int a[], int temp[], int l, int m, int r);
void mergeSort(int a[], int temp[], int l, int r);

This avoids repeated memory allocation and makes the algorithm significantly more efficient in practice.

Optimized Merge Sort in C++ (production-style implementation)

Below is an optimized version of the Merge Sort algorithm, written in a way that is commonly used in real-world and textbook implementations. The main improvement compared to the basic version is the use of a single auxiliary array, which significantly reduces memory overhead.

Main optimization ideas

• Only one temporary array is allocated.
• The temporary array is reused throughout the recursion.
• Only the segment [l ... r] is copied during merging.
• No unnecessary parameters are passed through recursive calls.

Optimized implementation

#include <iostream>
using namespace std;

// Merges two sorted subarrays:
// a[l..m] and a[m+1..r]
void merge(int a[], int temp[], int l, int m, int r)
{
    // Copy only the relevant segment into the temporary array
    for (int i = l; i <= r; i++)
        temp[i] = a[i];

    int i = l;      // pointer for left subarray
    int j = m + 1;  // pointer for right subarray
    int k = l;      // pointer for merged array

    // Merge elements back into the original array
    while (i <= m && j <= r)
    {
        if (temp[i] <= temp[j])
            a[k++] = temp[i++];
        else
            a[k++] = temp[j++];
    }

    // Copy remaining elements from the left subarray
    while (i <= m)
        a[k++] = temp[i++];

    // Remaining elements from the right subarray
    // are already in correct positions
}

// Recursive Merge Sort
void mergeSort(int a[], int temp[], int l, int r)
{
    if (l < r)
    {
        int m = l + (r - l) / 2;

        mergeSort(a, temp, l, m);       // sort left half
        mergeSort(a, temp, m + 1, r);   // sort right half
        merge(a, temp, l, m, r);        // merge halves
    }
}

// Utility function to print the array
void printArray(int a[], int n)
{
    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
    cout << endl;
}

int main()
{
    int a[] = {5, 3, 10, -34, 16, 4, 24, 11, -12, 14};
    int n = sizeof(a) / sizeof(a[0]);

    int temp[n]; // single auxiliary array

    mergeSort(a, temp, 0, n - 1);
    printArray(a, n);

    return 0;
}

Why this version is better

• Memory-efficient: only one auxiliary array of size n.
• Faster in practice: avoids repeated allocation and full-array copying.
• Clean recursion: no unnecessary parameters.
• Stable sorting: equal elements preserve their relative order.

Time and space complexity

• Time complexity:O(n log n) in all cases.
• Space complexity:O(n) due to the auxiliary array.

This makes Merge Sort a very reliable algorithm for large datasets, especially when predictable performance is required.

Further improvements (advanced topics)

• Switch to Insertion Sort for very small subarrays.
• Use iterative (bottom-up) Merge Sort to avoid recursion.
• Apply Merge Sort to linked lists where it becomes an in-place algorithm.