Merge Sort is an efficient sorting algorithm based on the divide-and-conquer paradigm. Its core principle is “divide and conquer” — breaking down a large problem into smaller subproblems, solving each subproblem, and then combining the results. Compared to simple sorting algorithms like Bubble Sort and Selection Sort, Merge Sort has a lower time complexity and is suitable for handling large-scale datasets.

Basic Idea of Merge Sort¶

Merge Sort consists of two main steps: Divide and Conquer.

1. Divide:
   Split the unsorted array into two halves, then recursively apply the “divide” operation to each half until each subarray contains a single element (or is empty). At this point, each subarray is naturally sorted (since a single element is trivially sorted).

Example:
Suppose we want to sort the array [5, 3, 8, 6, 2, 7, 1, 4]:
- First split into [5, 3, 8, 6] and [2, 7, 1, 4];
- Recursively split [5, 3, 8, 6] into [5, 3] and [8, 6], and [2, 7, 1, 4] into [2, 7] and [1, 4];
- Continue splitting until all subarrays contain one element: [5], [3], [8], [6], [2], [7], [1], [4].

2. Conquer:
   Merge two sorted subarrays into a larger sorted array. To merge, compare elements from both subarrays, take the smaller element at each step, and append it to the result array. Once one subarray is exhausted, append the remaining elements of the other subarray.

Example:
Merge the sorted subarrays [3, 5] and [6, 8]:
- Compare 3 and 6, take 3 → result [3];
- Compare 5 and 6, take 5 → result [3, 5];
- Left subarray remaining: [6, 8], right subarray is empty, append them → result [3, 5, 6, 8].

C++ Implementation of Merge Sort¶

The following C++ code implements Merge Sort with two core functions: mergeSort (recursive division) and merge (merging two sorted subarrays).

Step 1: Merge Function merge¶

The merge function merges two sorted subarrays into one sorted array.

void merge(vector<int>& arr, int low, int mid, int high) {
    int leftLen = mid - low + 1;  // Length of left subarray
    int rightLen = high - mid;    // Length of right subarray

    // Temporary arrays to store left and right subarrays
    vector<int> left(leftLen), right(rightLen);

    // Copy elements from arr to left subarray
    for (int i = 0; i < leftLen; i++) {
        left[i] = arr[low + i];
    }
    // Copy elements from arr to right subarray
    for (int i = 0; i < rightLen; i++) {
        right[i] = arr[mid + 1 + i];
    }

    // Merge left and right subarrays back into arr
    int i = 0, j = 0, k = low;  // i: left pointer, j: right pointer, k: arr pointer
    while (i < leftLen && j < rightLen) {
        if (left[i] <= right[j]) {  // Take the smaller element
            arr[k] = left[i];
            i++;
        } else {
            arr[k] = right[j];
            j++;
        }
        k++;
    }

    // Append remaining elements of left subarray
    while (i < leftLen) {
        arr[k] = left[i];
        i++;
        k++;
    }

    // Append remaining elements of right subarray
    while (j < rightLen) {
        arr[k] = right[j];
        j++;
        k++;
    }
}

Step 2: Merge Sort Function mergeSort¶

This function recursively divides the array and merges sorted subarrays.

void mergeSort(vector<int>& arr, int low, int high) {
    if (low < high) {  // Base case: stop when subarray has 1 element
        int mid = low + (high - low) / 2;  // Avoid overflow (equivalent to (low+high)/2)
        mergeSort(arr, low, mid);          // Recursively sort left half
        mergeSort(arr, mid + 1, high);     // Recursively sort right half
        merge(arr, low, mid, high);        // Merge the two sorted halves
    }
}

Step 3: Test Code¶

In the main function, call mergeSort and verify the result:

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

// [merge function and mergeSort function implementations here]

int main() {
    vector<int> arr = {5, 3, 8, 6, 2, 7, 1, 4};
    int n = arr.size();

    cout << "Array before sorting: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    mergeSort(arr, 0, n - 1);  // Invoke merge sort

    cout << "Array after sorting: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

Complete Merge Sort Process Example¶

For the array [5, 3, 8, 6, 2, 7, 1, 4], the sorting process is:

1. Division Process:
   - Initial array: [5, 3, 8, 6, 2, 7, 1, 4]
   - Split into [5, 3, 8, 6] and [2, 7, 1, 4]
   - Split [5, 3, 8, 6] into [5, 3] and [8, 6]
   - Split [5, 3] into [5] and [3]; split [8, 6] into [8] and [6]
   - Split [2, 7, 1, 4] into [2, 7] and [1, 4]
   - Split [2, 7] into [2] and [7]; split [1, 4] into [1] and [4]

2. Merge Process:
   - Merge [5] and [3] → [3, 5]
   - Merge [8] and [6] → [6, 8]
   - Merge [3, 5] and [6, 8] → [3, 5, 6, 8] (left half sorted)
   - Merge [2] and [7] → [2, 7]
   - Merge [1] and [4] → [1, 4]
   - Merge [2, 7] and [1, 4] → [1, 2, 4, 7] (right half sorted)
   - Merge [3, 5, 6, 8] and [1, 2, 4, 7] → [1, 2, 3, 4, 5, 6, 7, 8]

After running the code, the output will be the sorted array [1, 2, 3, 4, 5, 6, 7, 8], confirming the algorithm’s correctness.

Summary¶

Merge Sort achieves sorting through “divide-merge” steps. Its time complexity is O(n log n) (log n divisions, each merging n elements), and space complexity is O(n) (due to temporary arrays for merging). It is a stable and efficient algorithm, making it suitable for large datasets.

By modifying the input array and experimenting with different values, you can deepen your understanding of recursion and the merging process.