マージソートのベース条件

Question

マージソートを実装しようとしていますが、ベース条件の実装に問題があります。

私は2つのソートされた配列を取り込み、マージされた配列を返す関数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は既にソートされているため（単に多くの要素が1つ）、返されます。

Answer 3

選別方法は、2つの戻り条件有する：

• 基本条件を - すべき2つのソート配列がマージされてい

マージ方法 - 配列

条件をマージ

単一のアイテムを有します2つのソートされた配列を取り、1つのソートされた配列を返します。

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 
}