Merge Sort Algorithm in CPP

1. Introduction

Merge Sort is a divide-and-conquer sorting algorithm. It divides an unsorted list into N sub-lists, each containing one element (a list of one element is considered sorted). Then, it repeatedly merges these sub-lists to produce new sorted sub-lists until there is only one sub-list remaining. This will be the sorted list.

2. Implementation Steps

1. If the list has only one element, it's already sorted. Return it.

2. Split the list into two halves.

3. Recursively sort both halves.

4. Merge the two halves together (merge operation).

5. Return the merged, sorted list.

3. Implementation in C++ Programming

#include<iostream>
#include<vector>
// Function to merge two halves into a sorted data.
void merge(std::vector<int>& arr, int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    // Temp arrays to hold the two halves
    std::vector<int> L(n1);
    std::vector<int> 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[l..r]
    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++;
    }
    // Copy the remaining elements of L[], if any
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    // Copy the remaining elements of R[], if any
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}
// Function to perform merge sort
void mergeSort(std::vector<int>& arr, int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2; // Calculate mid point of array
        mergeSort(arr, l, m);   // Sort first half
        mergeSort(arr, m + 1, r); // Sort second half
        merge(arr, l, m, r);   // Merge the sorted halves
    }
}
int main() {
    std::vector<int> arr = {12, 11, 13, 5, 6, 7};
    int n = arr.size();
    mergeSort(arr, 0, n - 1);
    std::cout << "Sorted array: \n";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
    return 0;
}

Output:

Sorted array:
5 6 7 11 12 13

Explanation:

1. Merge Sort begins by ensuring that a single-element array is inherently sorted.

2. We then split our main array into two equal halves (or almost equal if the number of elements is odd).

3. Each half is recursively sorted using Merge Sort again.

4. After sorting both halves, we merge them. The merge operation ensures that the combined array is also sorted.

5. To merge the two halves, we maintain three pointers – one for each half and the third one for the main array. We compare the elements pointed by the half arrays and insert the smaller element into the main array.

6. This process continues until all elements in the two halves are merged and sorted in the main array.