java - 与 List 接口(interface)合并排序

Question

我编写了以下代码，但出现堆栈溢出。合并方法在单独测试时工作正常。当我现在查看代码时，我目光狭隘，无法理解为什么它不起作用，所以有人可以向我指出错误。非常感谢!

public static List<Comparable> mergeSort(List <Comparable> target){
    if(target.size() <  2)
        return target;

    return merge(mergeSort(copy(0,(target.size()-1)/2 + 1,target)),mergeSort(copy((target.size()-1)/2 + 1,target.size(),target)));
}

private static List<Comparable> merge(List<Comparable> target1,List<Comparable> target2){
    List <Comparable> result = new ArrayList <Comparable>();

    while(target1.size() > 0 || target2.size() > 0){
        if(target1.isEmpty()) 
            result.add(target2.remove(0));
        else if(target2.isEmpty()) 
            result.add(target1.remove(0));
        else if(target1.get(0).compareTo(target2.get(0)) < 0)
            result.add(target1.remove(0));
        else    
            result.add(target2.remove(0));
    }

   return result;
}

private static List<Comparable> copy(int startIndex, int endIndex, List<Comparable> target){
    List <Comparable> result = new ArrayList <Comparable>();

    for(int i = startIndex; i < endIndex; i++)
       result.add(target.get(i)); 

    return result;
}

Answer 1

我认为您的 mergeSort 实现的扩展性不太好。您正在使用您的copy方法将输入列表的适当范围复制为递归调用 mergeSort 的输入。如果考虑递归的整体深度，则每个级别都需要额外的空间，其大小相当于整个输入列表的大小。

这意味着您的代码需要 log2(n) 乘以 n 的内存，其中 n 是输入列表的大小。如果您要对大小为 65'536 个元素的列表进行合并排序，您的代码将创建它的副本，以便它将使用峰值量 log2(65'536) = 16 倍于输入表的内存要求。这很可能会导致 StackOverflowException .

为了解决这个问题，我会重写 mergeSort方法(或者更确切地说创建它的重载版本)来接受列表以及指向列表的下限和上限。这样，您就不需要在每个递归步骤中复制列表。另一方面，只要由下限和上限界定的范围仅包含一个元素，您就会返回一个新的 List仅包含此单个元素 merge()将运行。这样，您只需复制整个输入列表一次(即在最低递归级别)，并且最终将仅使用输入列表占用的内存的两倍(就复杂性而言， O(n) )。一旦merge()将传递这些单元素列表并创建一个新的中间结果列表，单元素列表将可用于 GC。