java中合并排序的问题

我是 stackoverflow 的新手，我需要一些帮助来编写一个程序来对可比数组列表进行合并排序。我已经在这段代码上工作了几个小时，但没有成功。该程序需要正确运行，因为我正在为计算机科学课程做它，而下一个作业要求我们测试不同类型的效率。这是代码：

合并方法：

public static void merge(ArrayList <Comparable> a, int first, int mid, int last){
    ArrayList <Comparable> b = new ArrayList();
    for(int k = first; k <= last; k++){
        b.add(a.get(k));
    }

    System.out.println("b now contains " + b);
    int middle =b.size() /2;
    for(int i = first; i <= last; i++){
        //System.out.println("mid: " + b.size() /2);
        //System.out.println("b: " + b);
        //System.out.println("a: " + a);
        //System.out.println("i: " + i);
        if(middle == b.size()){
            a.set(i, b.remove(0));
            middle--;
        }else if(middle == 0){
            a.set(0, b.remove(0));
        }else if(b.get(0).compareTo(b.get(middle)) < 0){
            System.out.println("moving " + b.get(0) + " from b[0] to a[" + 
                i + "] because " + b.get(0) + " is less than " + b.get(middle));
            a.set(i, b.remove(0));
            middle--;
            System.out.println("b now contains " + b);
        }else{
            System.out.println("moving " + b.get(middle) + " from b[" + 
                b.size() /2 + "] to a[" + i + "] because " + b.get(0) + 
                    " is greater than " + b.get(middle));
            a.set(i, b.remove(middle));
            //middle--;
            System.out.println("b now contains " + b);
        }
    }

    System.out.println();
    System.out.println("Merge");
    System.out.println(a);
    System.out.println();
}

归并排序方法：

public static void mergeSort(ArrayList <Comparable> a, int first, int last){
    if(first < last){
        int mid = first + (last - first) /2;
        System.out.println("mergeSorting " + a.subList(first, last + 1));
        mergeSort(a, first, mid);
        System.out.println("mergeSorting " + a.subList(first, mid + 1));
        mergeSort(a, mid + 1, last);
        System.out.println("merging " + a.subList(first, mid + 1) + 
            " and " + a.subList(mid + 1, last + 1));
        merge(a, first, mid, last);
    }
    System.out.println();
    System.out.println("base case");
    System.out.println();
}

我认为有一个问题merge方法，但我不确定。

我的代码似乎对列表进行了错误的排序，即：

Input:
[7,1,9,9,5,4,8,9,10,4] 

Output:
[4,8,9,4,10,10,5,9,9,7]

归并排序算法没问题。我刚刚定义了 ArrayList 的类型以避免警告

   public static void mergeSort(ArrayList <Comparable> a, int first, int last){
        if(first < last){
            int mid = first + (last - first) /2;
        //    System.out.println("mergeSorting " + a.subList(first, mid ));
            System.out.println("First"+first);
            System.out.println("Mid"+mid);
            System.out.println("Last"+last);
            System.out.println("MergeSortCall");
            System.out.println("firstVector " + a.subList(first, mid+1));
            System.out.println("secondVector " + a.subList(mid + 1,last+1));                
            mergeSort(a, first, mid);
            mergeSort(a, mid + 1, last);
            merge(a, first, mid, last);
            System.out.println("mergeVector " + a.subList(first,last+1));
        }

    }

第二部分确实很难确切地知道出了什么问题，所以我基本上使用您的符号将其替换为更简单的内容。请注意，第二部分只是一个“合并”算法。它应该非常简单。无论如何，使用这个你可以与你的结果进行比较（抱歉，很难理解第二部分的逻辑，这是你的作业，不是吗？）。我使用两个向量来提高可读性，但只需要像您一样的一个。

public static void merge(ArrayList <Comparable> a, int first, int mid, int last){
            ArrayList <Comparable> vectorFirst = new ArrayList<Comparable>();
            ArrayList <Comparable> vectorSecond = new ArrayList<Comparable>();

            for(int k=first;k<=mid;k++){
                vectorFirst.add(a.get(k));
            }
            for(int k=mid+1;k<=last;k++){
                vectorSecond.add(a.get(k));
            }

            int i=first;
            int j=mid+1;
            int k=first-1;
            while((i<=mid)&(j<=last)){
                if(vectorFirst.get(i-first).compareTo(vectorSecond.get(j-mid-1))==-1){
                    k=k+1;
                    a.set(k,vectorFirst.get(i-first));
                    i=i+1;
                }
                else{
                     k=k+1;
                     a.set(k,vectorSecond.get(j-mid-1));
                     j=j+1;
                }
            }
            if(i==mid+1){
                while(j<=last){
                    k=k+1;
                    a.set(k,vectorSecond.get(j-mid-1));
                    j=j+1;
                }
            }
            else{
                while(i<=mid){
                    k=k+1;
                    a.set(k,vectorFirst.get(i-first));
                    i=i+1;
                }
            }


        }