Untitled

// This function combines two sorted subarrays into one sorted array.
void combine(int arr[], int left, int mid, int right) {
    int size = right - left + 1;
    int* temp = new int[size];

    int i = left;      // Starting index for the left subarray
    int j = mid + 1;   // Starting index for the right subarray
    int k = 0;         // Index for the temporary array

    // Merge the two subarrays into temp[]
    while(i <= mid && j <= right) {
        if(arr[i] <= arr[j])
            temp[k++] = arr[i++];
        else
            temp[k++] = arr[j++];
    }

    // Copy any remaining elements from the left subarray
    while(i <= mid)
        temp[k++] = arr[i++];

    // Copy any remaining elements from the right subarray
    while(j <= right)
        temp[k++] = arr[j++];

    // Copy the sorted subarray back to the original array
    for(int p = 0; p < size; p++) {
        arr[left + p] = temp[p];
    }

    delete [] temp;
}

// This function recursively sorts the array using the above combine function.
void mysterySort(int arr[], int left, int right) {
    if(left < right) {
        int mid = left + (right - left) / 2;
        mysterySort(arr, left, mid);
        mysterySort(arr, mid + 1, right);
        combine(arr, left, mid, right);
    }
}