void mergeSort(int *arr, int *out, int start, int end) {
    if (end == start + 1) {
        out[0] = arr[start];
        return;
    }
    int mid = (start + end) / 2;
    int left_length = mid - start;
    int right_length = end - mid;
    int *left = new int[left_length];
    int *right = new int[right_length];
    mergeSort(arr, left, start, mid);
    mergeSort(arr, right, mid, end);
    // merge
    int i = 0;
    int j = 0;
    int k = 0;
    while (i < left_length && j < right_length) {
        if (left[i] <= right[j]) {
            out[k] = left[i];
            ++i;
        } else {
            out[k] = right[j];
            ++j;
        }
        ++k;
    }

    while (i < left_length) {
        out[k] = left[i];
        ++i;
        ++k;
    }
    while (j < right_length) {
        out[k] = right[j];
        ++j;
        ++k;
    }
    delete[] left;
    delete[] right;
}