MergeSort.cpp

#include <iostream>
#include <vector>

/**
 * Merge two sub-arrays of arr[]
 * - First sub-array is arr[left..mid]
 * - Second sub-array is arr[mid+1..right]
 *
 * @param arr   The array to be sorted
 * @param left  The left index of the first sub-array
 * @param mid   The right index of the first sub-array
 * @param right The right index of the second sub-array
 */

void merge(std::vector<int> &arr, int left, int mid, int right) {

  int n1 = mid - left + 1; // size of the first sub-array.
  int n2 = right - mid;    // size of the second sub-array.

  // create temporary arrays to hold the data
  std::vector<int> leftSubarray(n1);
  std::vector<int> rightSubarray(n2);

  // copy data to temporary arrays leftSubarray[] and rightSubarray[]
  for (int i = 0; i < n1; i++) {
    leftSubarray[i] = arr[left + i];
  }
  for (int j = 0; j < n2; j++) {
    rightSubarray[j] = arr[mid + 1 + j];
  }

  // merge the two sub-arrays back into the original array arr[]
  int i = 0, j = 0, k = left;

  while (i < n1 && j < n2) {
    if (leftSubarray[i] <= rightSubarray[j]) {
      arr[k] = leftSubarray[i];
      i++;
    } else {
      arr[k] = rightSubarray[j];
      j++;
    }
    k++;
  }

  // copy the remaining elements of leftSubarray[], if any
  while (i < n1) {
    arr[k] = leftSubarray[i];
    i++;
    k++;
  }

  // copy the remaining elements of rightSubarray[], if any
  while (j < n2) {
    arr[k] = rightSubarray[j];
    j++;
    k++;
  }
}

/**
 * Merge Sort algorithm
 *
 * @param arr   The array to be sorted
 * @param left  The left index of the sub-array to be sorted
 * @param right The right index of the sub-array to be sorted
 */

void mergeSort(std::vector<int> &arr, int left, int right) {
  if (left < right) {

    int mid = left + (right - left) / 2; // calculate the middle index

    // sort the first and second halves
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);

    // merge the sorted halves
    merge(arr, left, mid, right);
  }
}

int main() {

  std::vector<int> arr = {12, 11, 13, 5, 6, 7, 9, 4, 10, 9, 11, 1, 11};

  int arrSize = arr.size();

  std::cout << "Original array: ";
  for (int num : arr) {
    std::cout << num << " ";
  }
  std::cout << std::endl;

  mergeSort(arr, 0, arrSize - 1);

  std::cout << "Sorted array: ";
  for (int num : arr) {
    std::cout << num << " ";
  }
  std::cout << std::endl;

  return 0;
}