java - 使用递归进行归并排序

Question

我尝试实现递归合并排序，但出现堆栈溢出错误。

public class MergeSort {
    static int input[],mid;
    public static void mergeSort(int input[],int start,int end ){
        if(start>end){
            return;
        }
// dividing input array into two equal parts
        mid=(start+end)/2;
        mergeSort(input,start,mid);
        mergeSort(input,mid+1,end);
        merge(input,start,mid,end);
    }
    public static void merge(int input[],int start,int mid,int end )
    {
        int l[]=new int[mid-start+1];
        int r[]=new int[end-mid];
        for(int i=1;i<end-start+1;i++){
            l[i]=input[start+i-1];
        }
        for(int j=1;j<end-mid;j++){
            r[j]=input[mid+j];
        }

    l[end-start+2]='\u221e';// ASCII vlaue of infinity at the end of left array
    r[end-mid+1]='\u221e';//ASCII vlaue of infinity at the end of right array
    int i=1,j=1;
    for(int k=start;k<end;k++){
        if(l[i]<=r[j]){
            input[k]=l[i];
            i=i+1;
        }
        else{
            input[k]=r[j];
            j=j+1;
        }
    }

Answer 1

问题是你的终止条件:

    if(start > end){
        return;
    }
    // dividing input array into two equal parts
    mid=(start+end)/2;
    mergeSort(input,start,mid);   //  <= infinite recursion
    mergeSort(input,mid+1,end);

在第一次递归中，无法将 mid(下一个 end 值)减少到 小于 start 。例如，从范围 [0, 6] 开始，以下是第一次递归调用的 start, end 值序列:

0 6    mid = (0+6)/2 = 3
0 3    mid = (0+3)/2 = 1
0 1    mid = (0+1)/2 = 0
0 0    mid = (0+0)/2 = 0
0 0    mid = (0+0)/2 = 0
...

你永远不会到达开始>结束的点。无限递归。

也许 start >= end 对您有用？这使得您的基本情况成为一个只有 1 项的数组，而不是一个空数组。