合并排序中的基本条件

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 
}