void merge(int* arr, int from, int middle, int to) {
    int newSize = to - from + 1;
    int* temp = new int[newSize];

    int firstIndex = from;
    int secondIndex = middle + 1;
    int tempIndex = 0;
    while (firstIndex <= middle && secondIndex <= to) {
        if (arr[firstIndex] < arr[secondIndex]) {
            temp[tempIndex] = arr[firstIndex];
            tempIndex++;
            firstIndex++;
        }
        else {
            temp[tempIndex] = arr[secondIndex];
            tempIndex++;
            secondIndex++;
        }
    }

    while (firstIndex <= middle) {
        temp[tempIndex] = arr[firstIndex];
        tempIndex++;
        firstIndex++;
    }
    while (secondIndex <= to) {
        temp[tempIndex] = arr[secondIndex];
        tempIndex++;
        secondIndex++;
    }

    for (int copyIndex = from; copyIndex <= to; copyIndex++) {
        arr[copyIndex] = temp[copyIndex - from];
    }

    delete[] temp;
}

void mergeSort(int* arr, int from, int to) {
    if (to <= from) { // bottom of recursion
        return;
    }

    int middle = (from + to) / 2;
    mergeSort(arr, from, middle);
    mergeSort(arr, middle + 1, to);
    merge(arr, from, middle, to);
}