C++ Clan

Merge Sort

#include <iostream>
using namespace std;

int* Merge(int*, int*, const int, const int);

int* MergeSort(int* input, int start, int end, int& resultSize)
{
 if (end - start < 2)
 {
  int * result = new int[1];
  result[0] = input[start];
  resultSize = 1;
  return (result);
 }

 int leftSize = 0, rightSize = 0;

 int *left = MergeSort(input, start, (start + end) / 2, leftSize);
 int *right = MergeSort(input, (start + end) / 2, end, rightSize);

 int* result = Merge(left, right, leftSize, rightSize);
 resultSize = leftSize + rightSize;
 delete[] left;
 delete[] right;
 left = right = NULL; //to avoid dangling pointer
 return result;
}

int* Merge(int* left, int* right, const int leftSize, const int rightSize)
{
 int resultSize = leftSize + rightSize;
 int * result = new int[resultSize];
 int leftIndex = 0, rightIndex = 0, resultIndex = 0;

 while (rightIndex<rightSize && leftIndex<leftSize)
 {
  result[resultIndex++] = left[leftIndex] < right[rightIndex] ? left[leftIndex++] : right[rightIndex++];
 }
 while (rightIndex < rightSize)
  result[resultIndex++] = right[rightIndex++];
 while (leftIndex < leftSize)
  result[resultIndex++] = left[leftIndex++];
 return result;
}


void main()
{
 int* input = new int[20]{5, 34, 5, 6, 4, 56, 4, 3, 3, 5, 6, 4, 3, 5, 6, 87, 54, 3, 5, 76};

 int resultSize = 0;

 int* result = MergeSort(input, 0, 20, resultSize);
 for (size_t i = 0; i < resultSize; i++)
 {
  cout << endl << result[i];
 }
 delete[] input;

 delete[] result;

}