MergeSort2way.cpp

#include <iostream>
using namespace std;

void Merge(int* arr,int l, int m, int h)
{
    int size1 = m - l + 1;
    int size2 = h - m;
    int* arr1 = new int[size1];
    int* arr2 = new int[size2];
    int* arr3 = new int[size1 + size2];
    for (int i = 0; i < size1; i++)
    {
        arr1[i] = arr[l + i];
    }
    for (int i = 0; i < size2; i++)
    {
        arr2[i] = arr[m + 1 + i];
    }
    int i = 0, j = 0, k = 0;
    while (i < size1 && j < size2)
    {
        if (arr1[i] < arr2[j])
        {
            arr3[k] = arr1[i];
            i++;
        }
        else
        {
            arr3[k] = arr2[j];
            j++;
        }
        k++;
    }
    while(i < size1){
        arr3[k] = arr1[i];
        i++;
        k++;
    }
    while(j < size2){
        arr3[k] = arr2[j];
        j++;
        k++;
    }
    for (int a = 0; a < size1 + size2; a++)
    {
        arr[l + a] = arr3[a];
    }
    delete[] arr1;
    delete[] arr2;
}
void MergeSort(int* arr,int low, int high){
    int mid;
    //if true, then arr contains more than 1 element
    if (low < high)
    {
        //break the array in 2 parts
        mid = (low + high)/2;
        MergeSort(arr,low,mid);
        MergeSort(arr,mid+1,high);
        Merge(arr,low,mid,high);
    }
    
}
void display(int *arr, int size)
{
    for (size_t i = 0; i < size; i++)
    {
        cout << arr[i] << " ";
    }
}
int main(int argc, char const *argv[])
{
    int arr[8] = {9,3,7,5,6,4,8,2};
    MergeSort(arr,0,7);
    display(arr,8);
    return 0;
}