mergesort

#include <iostream>
#include <stdlib.h>

using namespace std;

void merge(long* arr, int l, int m, int r) {
    // Create new arrays for left and right partitions
    int lSize = m - l;
    int rSize = r - m;
    long* lPart = new long[lSize];
    long* rPart = new long[rSize];

    // Copy elements into their respective partitions.
    for (int i = 0; i < lSize; i++) {
        lPart[i] = arr[i + l];
    }

    for (int i = 0; i < rSize; i++) {
        rPart[i] = arr[i + m];
    }

    // Add elements from new partitions back into new array, sorted
    //     until one of the arrays reaches the end.
    int lIdx = 0;
    int rIdx = 0;
    int arrIdx = l;

    while (lIdx < lSize && rIdx < rSize) {
        if (lPart[lIdx] <= rPart[rIdx]) {
            arr[arrIdx] = lPart[lIdx];
            lIdx++;
        } else if (rPart[rIdx] <= lPart[lIdx]) {
            arr[arrIdx] = rPart[rIdx];
            rIdx++;
        }
        arrIdx++;
    }

    // Finish off the remaining elements in the right and left arrays
    while (lIdx < lSize) {
        arr[arrIdx++] = lPart[lIdx++];
    }

    while (rIdx < rSize) {
        arr[arrIdx++] = rPart[rIdx++];
    }
}

void mergeSort(long* arr, int size) {
    for (int partitionSize = 1; partitionSize < size; partitionSize *= 2) {

        for (int left = 0; left < size - 1; left += partitionSize * 2) {

            int mid = min(left + partitionSize, size);
            int right = min(left + partitionSize * 2, size);
            merge(arr, left, mid, right);
        }
    }
}


int main() {
    long arr[] = {8, 2, 3, 7, 6, 5, 4, 2, 7};
    mergeSort(arr, 9);
    for (int i = 0; i < 9; i++) {
        cout << arr[i] << " ";
    }
}