合併排序中的基本條件

Question

我想實現合併排序，並且在執行基本條件時遇到了問題。

我有一個函數merge它需要兩個有序數組並返回一個合併數組。

int[] merge(int[] a , int[] b) 

現在我的歸併排序例程如下

private static int[] mergeSort(int[] a, int low , int high) 
{ 
    int mid = (low + high) /2; 
    if (low < high) 
    { 
     return merge(mergeSort(a,low, mid-1), mergeSort(a, mid , high)); 
    } 
    return //return what ? 
} 

什麼是這裏的基礎條件？我在犯什麼錯誤？

Answer 1

基本條件是當你有單個元素列表a，它根據定義已經排序。只需返回它。

Answer 2

只需返回a，因爲它已經排序（它至多包含一個元素）。

Answer 3

分揀方法有兩個返回的條件：

• 鹼的條件 - 在陣列僅具有單個項目
• 合併條件 - 兩個已排序的陣列已經合併

合併應方法接受兩個有序數組並返回一個有序數組。

public int[] sort(int[] input){ 
    int mid = input.length/2; 
    if(input.length > 1){ 
    // create and populate left and right arrays to merge 
    // left => input[0 > mid-1] 
    // right => input[mid > input.length] 
    return merge(sort(left), sort(right)); 
    } 
    return input; 
} 

public int[] merge(int[] left, int[] right){ 
    // your merge logic 
}