mergeSort.cpp

/* 
 * Author: Antonello Galipò
 * Merge sort implementation in c++
*/
#include <iostream>
using std::cout;
using std::endl;
using std::string;
using std::memcpy;

void mergeSort(int *array, int *temp, int leftStart, int rightEnd);
void mergeHalves(int *array, int *temp, int leftStart, int rightEnd);
void mergeArrays(int *a, int *temp, int left, int center, int right);

    void printArray(int *array, int size, string message)
{
    cout<<message<<endl;
    for (int i = 0; i < size; i++)
        cout << array[i] << "\t";
    cout << endl;
}
int main(){
    const int size = 10;
    int myInts[size] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
    int temp[size] = {0};
    printArray(myInts,size,"Input");
    mergeSort(myInts, temp, 0, size-1);
    printArray(myInts, size, "Output:");

    return 0;
}

void mergeSort(int *array, int *temp, int leftStart, int rightEnd){
    if (leftStart >= rightEnd)
        return;

    int middle = (leftStart + rightEnd) / 2;

    mergeSort(array, temp, leftStart, middle);
    mergeSort(array, temp, middle + 1, rightEnd);
    mergeHalves(array,temp,leftStart,rightEnd);
    return;
}

void mergeHalves(int *array, int *temp, int leftStart, int rightEnd){
    int leftEnd = (rightEnd + leftStart) / 2;
    int rightStart = leftEnd + 1;
    int size = rightEnd - leftStart + 1;

    int left = leftStart;
    int right = rightStart;
    int index = leftStart;

    while (left <= leftEnd && right <= rightEnd){
        if (array[left] <= array[right]){
            temp[index] = array[left];
            left++;
        }else{
            temp[index] = array[right];
            right++;
        }
        index++;
    }

    memcpy(temp + index, array + left, (leftEnd - left + 1) * sizeof(int));
    memcpy(temp + index, array + right, (rightEnd - right + 1) * sizeof(int));
    memcpy(array + leftStart, temp + leftStart, size * sizeof(int));
}