实现MergeSort

Question

我已经实现了一个MergeSorting，它接受一个泛型数据类型和一个上下索引界限，在超过这些界限后停止排序。示例{85,31,321,6549,123,2,1,0} lower =0 upper =4将生成31,85,123,321,6549,2,1,0。虽然当我测试我的代码时，它给出了一个堆栈溢出错误，我不知道为什么。

我已经检查了我的代码，但找不到问题，也许我没有一个边缘情况来打破递归调用。

import java.util.ArrayList;
public class Sorts<T extends Comparable<? super T>> {
   public void merge(ArrayList<T> list, int start, int mid, int end)
   {
        ArrayList<T> tempArr = new ArrayList<T>(end - start);
        int leftidx = start;
        int rightidx = mid;
        while(true)
        {
            if (leftidx ==  mid)
            {
                tempArr.addAll(list.subList(rightidx,end)); 

                break;
            }
            else if (rightidx == end)
           {
                tempArr.addAll(list.subList(leftidx, mid));
                break;
           }

           T left = list.get(leftidx);
           T right = list.get(rightidx);

           int check = left.compareTo(right);

           if (check < 0) 
           {
               tempArr.add(left); 
               leftidx++; 
           }
           else
           {
               tempArr.add(right); 
               rightidx++; 
           }
        }

        for (int j = 0; j < tempArr.size(); j++)
        {
            list.set(start + j, tempArr.get(j));
        }




}
public void MergeSort(ArrayList<T> list, int start, int end) {

    int median = start + (end - start) / 2;
    MergeSort(list, start, median);
    MergeSort(list, median, end);
    merge(list, start, median, end);

   }
}

当我运行一个测试时，在我mergesort类中的MergeSort(list，start，median)第82行给出了一个错误"java.lang.StackOverflowError“。我的测试类是：

public class SortsTester extends Sorts{
    public void mergeSortTester{
       Integer [] arr = {85,31,321,6549,123,2,1,0};
       ArrayList<Integer> ranArrLst = new ArrayList<>(Arrays.asList(arr));
       MergeSort(ranArrLst,0,7);
       System.out.println(Arrays.toString(ranArrLst.toArray()));
     }
}

Answer 1

当元素少于两个时，您不应在MergeSort中执行任何操作：

public void MergeSort(ArrayList<T> list, int start, int end) {
    if ((end - start) < 2) {
        return;
    }
    int median = start + ((end - start) / 2);
    MergeSort(list, start, median);
    MergeSort(list, median, end);
    merge(list, start, median, end);
}