Merge Sort Algorithm in C++

Merge Sort is a Divide and Conquer Algorithm. It continuously divides in 2 the array, and then each divided part and so on until we have all the values separated, and then starts grouping the values, and sorting them in small groups. This means that the problem is divided into small parts, and those small parts are solved and then merged.

// Merge Sort

#include <iostream>
using namespace std;

void mergeElements(int arrayOfNumbers[], int left, int middle, int right)
{
    int noElemLeftAray = middle - left + 1;
    int noElemRightAray =  right - middle;

    // Temporary arrays of halves
    int leftArray[noElemLeftAray], rightArray[noElemRightAray];

    // Copy the values in the 2 new arrays
    for (int i = 0; i < noElemLeftAray; i++)
    {
        leftArray[i] = arrayOfNumbers[left + i];
    }

    for (int j = 0; j < noElemRightAray; j++)
    {
        rightArray[j] = arrayOfNumbers[middle + 1 + j];
    }


    // Merge the arrays back
    int indexLeftSubArray = 0;
    int indexRightSubArray = 0;
    int indexMergedSubarray = left;
    while (indexLeftSubArray < noElemLeftAray && indexRightSubArray < noElemRightAray)
    {
        if (leftArray[indexLeftSubArray] <= rightArray[indexRightSubArray])
        {
            arrayOfNumbers[indexMergedSubarray] = leftArray[indexLeftSubArray];
            indexLeftSubArray++;
        }
        else
        {
            arrayOfNumbers[indexMergedSubarray] = rightArray[indexRightSubArray];
            indexRightSubArray++;
        }
        indexMergedSubarray++;
    }

    // Copy the remaining elements in the left array
    while (indexLeftSubArray < noElemLeftAray)
    {
        arrayOfNumbers[indexMergedSubarray] = leftArray[indexLeftSubArray];
        indexLeftSubArray++;
        indexMergedSubarray++;
    }

    // Copy the remaining elements in the right array
    while (indexRightSubArray < noElemRightAray)
    {
        arrayOfNumbers[indexMergedSubarray] = rightArray[indexRightSubArray];
        indexRightSubArray++;
        indexMergedSubarray++;
    }
}

void mergeSort(int arrayOfNumbers[], int left, int right)
{
    if (left < right)
    {
        int middle = left + (right - left) / 2;

        // Sort and merge the first and second halves
        mergeSort(arrayOfNumbers, left, middle);
        mergeSort(arrayOfNumbers, middle + 1, right);

        mergeElements(arrayOfNumbers, left, middle, right);
    }
}

void printElementsOfArray(int arrayOfNumbers[], int numberOfElements)
{
  for (int i = 0; i < numberOfElements; ++i)
  {
    cout << arrayOfNumbers[i] << " ";
  }
  cout << endl;
}

int main(void)
{
  int arrayOfNumbers[] = {4, 7, 9, 3, 21, 18, 23, 15, 8, 17};
  int numberOfElements = sizeof(arrayOfNumbers) / sizeof(arrayOfNumbers[0]);
  int startIndex = 0;
  int lastIndex = numberOfElements - 1;

  mergeSort(arrayOfNumbers, startIndex, lastIndex);
  cout<<"The sorted array is: \n";
  printElementsOfArray(arrayOfNumbers, numberOfElements);
}