Implementation of Merge Sort in CPP Programming Language

Merge Sort is one of the most efficient and widely used sorting algorithms. It follows the divide-and-conquer approach, which means it breaks down a problem into smaller subproblems, solves them, and then combines the results. Merge Sort is particularly useful because it guarantees a time complexity of O(n log n) in all cases, making it a reliable choice for sorting large datasets.

In this article, we will briefly touch upon how Merge Sort works, go through its implementation in C++ and understand the implementation.

How Merge Sort Works

Merge Sort works by recursively dividing the input array into smaller subarrays until each subarray contains only one element. Then, it keeps merging these subarrays in a sorted order. Here’s a step-by-step breakdown:

Divide: Split the array into two halves.
Conquer: Recursively sort each half.
Combine: Merge the two sorted halves into a single sorted array.

Refer to these articles for better understanding on how merge sort algorithm works:

Implementation of Merge Sort Algorithm in C++

Here’s the implementation of Merge Sort Algorithm in C++:


#include <iostream>
#include <vector>

class MergeSort {
public:
  /**
   * Recursively sorts the array using the merge sort algorithm.
   * 
   * @param arr   The array to be sorted.
   * @param left  The starting index of the array segment to be sorted.
   * @param right The ending index of the array segment to be sorted.
   */
  static void mergeSort(std::vector<int>& arr, int left, int right) {
    if (left < right) {
      // Find the middle point to divide the array into two halves
      int mid = left + (right - left) / 2;
      
      // Recursively sort the left half of the array
      mergeSort(arr, left, mid);
      
      // Recursively sort the right half of the array
      mergeSort(arr, mid + 1, right);
      
      // Merge the two sorted halves
      merge(arr, left, mid, right);
    }
  }

private:
  /**
   * Merges two sorted subarrays into a single sorted array.
   * 
   * @param arr   The array containing the two subarrays to be merged.
   * @param left  The starting index of the first subarray.
   * @param mid   The ending index of the first subarray.
   * @param right The ending index of the second subarray.
   */
  static void merge(std::vector<int>& arr, int left, int mid, int right) {
    // Calculate the sizes of the two subarrays
    int n1 = mid - left + 1;  // Size of the left subarray
    int n2 = right - mid;     // Size of the right subarray

    // Create temporary vectors to hold the two subarrays
    std::vector<int> L(n1);
    std::vector<int> R(n2);

    // Copy data to temporary vectors
    for (int i = 0; i < n1; i++)
      L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
      R[j] = arr[mid + 1 + j];

    // Initialize indices for the subarrays and the main array
    int i = 0;  // Index for the left subarray (L)
    int j = 0;  // Index for the right subarray (R)
    int k = left;  // Index for the main array (arr)

    // Merge the two subarrays back into the main array
    while (i < n1 && j < n2) {
      if (L[i] <= R[j]) {
        // If the current element in L is smaller, add it to the main array
        arr[k] = L[i];
        i++;
      } else {
        // If the current element in R is smaller, add it to the main array
        arr[k] = R[j];
        j++;
      }
      k++;
    }

    // Copy any remaining elements from the left subarray (if any)
    while (i < n1) {
      arr[k] = L[i];
      i++;
      k++;
    }

    // Copy any remaining elements from the right subarray (if any)
    while (j < n2) {
      arr[k] = R[j];
      j++;
      k++;
    }
  }
};

// Helper function to print a vector
void printVector(const std::vector<int>& arr) {
  std::cout << "[";
  for (size_t i = 0; i < arr.size(); i++) {
    std::cout << arr[i];
    if (i < arr.size() - 1) std::cout << ", ";
  }
  std::cout << "]";
}

// Example usage
int main() {
  // Define the vector to be sorted
  std::vector<int> arr = {4, 1, 2, 3};
  
  // Print the original vector
  std::cout << "Original array: ";
  printVector(arr);
  std::cout << std::endl;
  
  // Call the mergeSort function to sort the vector
  MergeSort::mergeSort(arr, 0, arr.size() - 1);
  
  // Print the sorted vector
  std::cout << "Sorted array: ";
  printVector(arr);
  std::cout << std::endl;
  
  return 0;
}

Explanation of the Implementation

Let’s break down the merge sort implementation step by step to understand how it works.

The `mergeSort` Method

The mergeSort method is the main method that performs the sorting. It takes three parameters:

arr: Reference to the vector to be sorted.
left: The starting index of the segment of the vector to be sorted.
right: The ending index of the segment of the vector to be sorted.

Here’s how it works:

Base Condition: The method first checks if left < right. This condition ensures that the array has more than one element. If left is not less than right, it means the array has either one or zero elements, and no sorting is needed.
Divide the Array: If the array has more than one element, the method calculates the middle index (mid) using the formula left + (right - left) / 2. This divides the array into two halves and avoids potential integer overflow.
Recursive Calls: The method then calls itself recursively to sort the left half (mergeSort(arr, left, mid)) and the right half (mergeSort(arr, mid + 1, right)). This process continues until the array is divided into single-element subarrays.
Merge the Sorted Halves: Once the two halves are sorted, the merge method is called to merge them back into a single sorted array.

The `merge` Method

The merge method is responsible for merging two sorted subarrays into a single sorted array. It takes four parameters:

arr: Reference to the vector containing the two subarrays to be merged.
left: The starting index of the first subarray.
mid: The ending index of the first subarray.
right: The ending index of the second subarray.

Here’s how it works:

Calculate Subarray Sizes: The sizes of the two subarrays are calculated using n1 = mid - left + 1 (size of the left subarray) and n2 = right - mid (size of the right subarray).
Create Temporary Vectors: Two temporary vectors, L and R, are created to hold the elements of the left and right subarrays. The elements are copied from the main array to these temporary vectors.
Merge Process: The method then merges the two subarrays back into the main array (arr). It uses three indices:
- i: Index for the left subarray (L).
- j: Index for the right subarray (R).
- k: Index for the main array (arr).
The method compares the elements of L and R one by one. The smaller element is placed into the main array, and the corresponding index (i or j) is incremented. This process continues until all elements from either L or R are placed into the main array.
Copy Remaining Elements: If there are any remaining elements in L or R, they are copied directly into the main array.

Example Run

Let’s walk through an example with the vector [4, 1, 2, 3]:

The mergeSort method is called with left = 0 and right = 3.
The array is divided into two halves: [4, 1] and [2, 3].
Each half is further divided and sorted recursively:
- [4, 1] becomes [4] and [1], which are merged into [1, 4].
- [2, 3] becomes [2] and [3], which are merged into [2, 3].
Finally, the two sorted halves [1, 4] and [2, 3] are merged into the final sorted array [1, 2, 3, 4].