Merge Sort

void Merge(long long int *arr, int left, int middle, int right)
{
    int i;
    int l_idx = left;
    int r_idx = middle + 1;
    int idx = left;
    int *temp_arr = (int *)malloc(sizeof(int) * (right + 1));
 
    while ((l_idx <= middle) && (r_idx <= right))
    {
        if (arr[l_idx] > arr[r_idx]) temp_arr[idx++] = arr[r_idx++];
        else temp_arr[idx++] = arr[l_idx++];
    }
 
    while (l_idx <= middle) temp_arr[idx++] = arr[l_idx++];
    while (r_idx <= right) temp_arr[idx++] = arr[r_idx++];
 
    for (i = left; i <= right; i++)
        arr[i] = temp_arr[i];
 
    free(temp_arr);
}
 
void MergeSort(long long int *arr, int left, int right)
{
    if (left < right)
    {
        int middle = (left + right) / 2;
        MergeSort(arr, left, middle);
        MergeSort(arr, middle + 1, right);
        Merge(arr, left, middle, right);
    }
}