Merge Sort in C++

Merge Sort in C++ is a popular sorting algorithm that divides the input array into smaller subarrays, recursively sorts them, and then merges them to produce a sorted output in ascending or descending order.

Here’s the pseudo code for the Merge Sort algorithm in C++:

void Merge(int arr[], int left, int mid, int right) {
    // Merge two sorted subarrays.
    // ...
}
 
void MergeSort(int arr[], int left, int right) {
    if (left >= right) {
        return;
    }
 
    int mid = left + (right - left) / 2;
    MergeSort(arr, left, mid);
    MergeSort(arr, mid + 1, right);
    Merge(arr, left, mid, right);
}

The MergeSort function recursively divides the array into smaller parts and then merges them back together using the Merge function. The Merge function combines two sorted subarrays into a single sorted array.

Let’s understand how Merge Sort works with a simple example:

Consider an unsorted array: [38, 27, 43, 3, 9, 82, 10]

Step 1: Divide

• The array is divided into two halves: [38, 27, 43] and [3, 9, 82, 10]

Step 2: Conquer

• Each individual subarray is sorted:
• [38, 27, 43] -> [27, 38, 43]
• [3, 9, 82, 10] -> [3, 9, 10, 82]

Step 3: Merge

• The sorted subarrays are merged: [27, 38, 43] and [3, 9, 10, 82] are merged into [3, 9, 10, 27, 38, 43, 82]

Step 4: Repeat

• The process is repeated recursively for the merged array until the entire array is sorted.
• The final sorted array is [3, 9, 10, 27, 38, 43, 82].

This program is successfully run on Dev-C++ using TDM-GCC 4.9.2 MinGW compiler on a Windows system.

/*
 * C++ Program to Implement Merge Sort
 */
 
#include <iostream>
 
using namespace std;
 
// A function to merge the two half into a sorted data.
void Merge(int *a, int low, int high, int mid)
{
    // We have low to mid and mid+1 to high already sorted.
    int i, j, k, temp[high-low+1];
    i = low;
    k = 0;
    j = mid + 1;
 
    // Merge the two parts into temp[].
    while (i <= mid && j <= high)
    {
        if (a[i] < a[j])
        {
            temp[k] = a[i];
            k++;
            i++;
        }
        else
        {
            temp[k] = a[j];
            k++;
            j++;
        }
    }
 
    // Insert all the remaining values from i to mid into temp[].
    while (i <= mid)
    {
        temp[k] = a[i];
        k++;
        i++;
    }
 
    // Insert all the remaining values from j to high into temp[].
    while (j <= high)
    {
        temp[k] = a[j];
        k++;
        j++;
    }
 
    // Assign sorted data stored in temp[] to a[].
    for (i = low; i <= high; i++)
    {
        a[i] = temp[i-low];
    }
}
 
// A function to split array into two parts.
void MergeSort(int *a, int low, int high)
{
    int mid;
    if (low < high)
    {
        mid=(low+high)/2;
        // Split the data into two half.
        MergeSort(a, low, mid);
        MergeSort(a, mid+1, high);
 
        // Merge them to get sorted output.
        Merge(a, low, high, mid);
    }
}
 
int main()
{
    int n, i;
    cout<<"\nEnter the number of data element to be sorted: ";
    cin>>n;
 
    int arr[n];
    for(i = 0; i < n; i++)
    {
        cout<<"Enter element "<<i+1<<": ";
        cin>>arr[i];
    }
 
    MergeSort(arr, 0, n-1);
 
    // Printing the sorted data.
    cout<<"\nSorted Data ";
    for (i = 0; i < n; i++)
    cout<<"->"<<arr[i];
 
    return 0;
}

1. Take input of data.
2. Call MergeSort() function.
3. Recursively split the array into two equal parts.
4. Split them until we get at most one element in both half.
5. Combine the result by invoking Merge().
6. It combines the individually sorted data from low to mid and mid+1 to high.
7. Return to main and display the result.
8. Exit.

In this case, we are entering the elements to be sorted using Merge Sort: “23, 987, 45, 65, 32, 9, 475, 1, 17, and 3.”

Enter the number of data element to be sorted: 10
Enter element 1: 23
Enter element 2: 987
Enter element 3: 45
Enter element 4: 65
Enter element 5: 32
Enter element 6: 9
Enter element 7: 475
Enter element 8: 1
Enter element 9: 17
Enter element 10: 3
 
Sorted Data ->1->3->9->17->23->32->45->65->475->987

Time Complexity: O(n log n)
The time complexity of Merge Sort is O(n log n) for all cases. It divides the array into halves recursively and merges them, and the merging process takes O(n).

Space Complexity: O(n)
The space complexity is O(n) as it requires additional memory to store the temporary array during merging.

• Stable sorting algorithm, maintains the relative order of equal elements.
• Efficient for large datasets with a time complexity of O(n log n).
• Predictable performance, consistently performs well regardless of input data.
• No worst-case scenarios, guarantees reliable sorting performance.
• Memory-efficient, doesn’t require additional memory space for sorting.

• Merge sort uses more memory to sort data.
• It doesn’t sort data in the same memory location (not in-place).
• It may not be the best choice for small lists.

To practice programs on every topic in C++, please visit “Programming Examples in C++”, “Data Structures in C++” and “Algorithms in C++”.