C++ Program to Implement Merge Sort

1. Introduction

Merge Sort is a divide-and-conquer sorting algorithm that consistently splits a list into two halves. If the list is already singular in nature (only one element), it's considered sorted. Otherwise, each half is recursively sorted and then merged back together. 

During the merging process, the two halves are combined in a sorted manner to produce a single sorted list. This method ensures that the entirety of the original list becomes sorted. The efficiency of Merge Sort makes it a favored choice for many computational tasks, particularly when stability is desired.

In this blog post, we will learn how to write a C++ program to implement the Merge Sort algorithm.

2. Program Overview

1. Divide the list into halves recursively, until each sub-list consists of a single element.

2. Merge these sub-lists iteratively to form sorted lists, until only one sorted list remains.

3. Code Program

#include <iostream>
using namespace std;

// Function for merging two sorted arrays
void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;

    int L[n1], R[n2];

    // Copy data to temp arrays L[] and R[]
    for (int i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    // Merge the temp arrays back into arr[]
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

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

        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        merge(arr, l, m, r);
    }
}

int main() {
    int n;
    cout << "Enter the number of elements: ";
    cin >> n;
    int arr[n];

    cout << "Enter the elements: ";
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    mergeSort(arr, 0, n - 1);

    cout << "Sorted array: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;

    return 0;
}

Output:

Enter the number of elements: 6
Enter the elements: 12 11 13 5 6 7
Sorted array: 5 6 7 11 12 13

4. Step By Step Explanation

1. The 'merge' function handles the task of merging two sorted sub-arrays.

2. The 'mergeSort' function sorts the array by recursively dividing and merging.

3. The 'main' function first takes the array size and elements as input from the user, and then sorts it using 'mergeSort'.