MergeSort.cpp

#include <iostream>
using namespace std;

void merge(int* array, int* leftArray, int leftSize, int* rightArray, int rightSize) {
    int i = 0, l = 0, r = 0;

    while (l < leftSize && r < rightSize) {
        if (leftArray[l] < rightArray[r]) {
            array[i++] = leftArray[l++];
        }
        else {
            array[i++] = rightArray[r++];
        }
    }

    while (l < leftSize) array[i++] = leftArray[l++];
    while (r < rightSize) array[i++] = rightArray[r++];
}

void MergeSort(int* array, int size) {
    if (size <= 1) return;

    int middle = size / 2;
    int* leftArray = new int[middle];
    int* rightArray = new int[size - middle];

    for (int i = 0; i < middle; i++) leftArray[i] = array[i];
    for (int i = middle; i < size; i++) rightArray[i - middle] = array[i];

    MergeSort(leftArray, middle);
    MergeSort(rightArray, size - middle);
    merge(array, leftArray, middle, rightArray, size - middle);

    delete[] leftArray;
    delete[] rightArray;
}

int main() {
    int array[] = { 3,2,7,1,4,9,8,6,5 };
    int size = sizeof(array) / sizeof(array[0]);

    MergeSort(array, size);

    for (int i = 0; i < size; i++) {
        cout << array[i] << " ";
    }
}