合并排序程序超出时间限制

Question

我尝试实现合并排序，但收到“超出时间限制”错误。 我在 GeeksForGeeks 平台上尝试过这个。该代码几乎适用于所有测试用例。 有没有办法优化代码？

这是我的代码：

void merge(int arr[], int l, int m, int r)
{ 
    int n = arr.length; 
    int b[] = new int[n];
    
    int i = l;
    int j = m + 1;
    int k = l;
    
    while (i <= m && j <= r) {
        if (arr[i] < arr[j]) {
            b[k] = arr[i]; 
            i++;
        } else {
            b[k] = arr[j];
            j++;
        }
        k++;
    }
    
    if (i > m) {
        while (j <= r) {
            b[k] = arr[j];
            k++;
            j++;
        } 
    } else {
        while(i <= m) {
            b[k] = arr[i];
            k++;
            i++;
        }
    }
    
    for (k = l; k <= r; k++) {
        arr[k] = b[k];
    }
}

void mergeSort(int arr[], int l, int r)
{
    if (l > r) {
        return;
    }
    
    if (l < r) {
        int mid = (l + r) / 2;
        mergeSort(arr, l, mid);
        mergeSort(arr, mid + 1, r);
        merge(arr, l, mid, r);
    }
}

Answer 1

更改代码以一次性分配第二个数组，而不是在每次合并时分配。此示例执行一次复制，然后与每一级递归交替合并方向以避免复制回来。 mergeSort是入口函数，mergeSortR是递归函数：

static void mergeSort(int a[], int l, int r)
{
    r += 1;                             // change r to end (last+1)
    if((r-l) < 2)                       // return if nothing to sort
        return;
    int [] b = a;                       // one time copy
    mergeSortR(b, a, l, r);
}

static void mergeSortR(int b[], int a[], int bb, int ee)
{
    if ((ee - bb) == 1)                 // if one element, return
        return;
    int mm = (bb+ee)/2;                 // midpoint, start of right half
    mergeSortR(a, b, bb, mm);           // sort left  half of a to b
    mergeSortR(a, b, mm, ee);           // sort right half of a to b
    merge(b, a, bb, mm, ee);            // merge b to a
}

static void merge(int a[], int b[], int bb, int mm, int ee)
{
    int o = bb;                         // b[]       index
    int l = bb;                         // a[] left  index
    int r = mm;                         // a[] right index
    while(true){                        // merge data
        if(a[l] <= a[r]){               // if a[l] <= a[r]
            b[o++] = a[l++];            //   copy a[l]
            if(l < mm)                  //   if not end of left run
                continue;               //     continue (back to while)
            while(r < ee)               //   else copy rest of right run
                b[o++] = a[r++];
            break;                      //     and return
        } else {                        // else a[l] > a[r]
            b[o++] = a[r++];            //   copy a[r]
            if(r < ee)                  //   if not end of right run
                continue;               //     continue (back to while)
            while(l < mm)               //   else copy rest of left run
                b[o++] = a[l++];
            break;                      //     and return
        }
    }
}