java fork/join mergesort已更新以方便複製

Question

我創建了一個完整的，可運行的示例，它重現了沒有實際按mergesort排序的列表的錯誤。什麼是打印到控制檯22， 22， 22， 1， 1， 1， -2， -2， -2， 1， 22， -2， 1， 22， -2。所以似乎mergesort從不影響列表的後半部分，而前半部分只是因爲insertSort被成功調用而被排序。任何幫助和建議表示讚賞。謝謝！

package threadedmergesort; 

import java.util.ArrayList; 
import java.util.Comparator; 
import java.util.concurrent.ForkJoinPool; 
import java.util.concurrent.RecursiveAction; 

public class ThreadedMergeSort implements Comparator<Integer>{ 

    public static void main(String[] args) { 
     ArrayList<Integer> toSort = new ArrayList<Integer>(); 
     toSort.add(1); 
     toSort.add(22); 
     toSort.add(-2); 
     toSort.add(1); 
     toSort.add(22); 
     toSort.add(-2); 
     toSort.add(1); 
     toSort.add(22); 
     toSort.add(-2); 
     toSort.add(1); 
     toSort.add(22); 
     toSort.add(-2); 
     toSort.add(1); 
     toSort.add(22); 
     toSort.add(-2); 
     toSort.add(1); 
     toSort.add(22); 
     toSort.add(-2); 

     ThreadedMergeSort.sort(toSort, 0, toSort.size()-11); 
     for (Integer e: toSort){ 
       System.out.println(e); 
       } 
    } 

    public static void sort (ArrayList<Integer> inputComp){ 
     sort(inputComp, 0, inputComp.size()-1); 
    } 
    public static void sort (ArrayList<Integer> inputComp, int low, int high){ 
     if (high-low< SIZE_LIMIT){ 
      insertionSort(inputComp, low, high); 
      return; 
     } 
     ArrayList<Integer> temp = new ArrayList(inputComp.size()); 
     pool.invoke(new SortTask(inputComp, temp, low, high)); 
     System.out.println("pool.invoke"); 
    } 

    static class SortTask extends RecursiveAction{ 
     ArrayList<Integer> inputComp; 
     ArrayList<Integer> temp; 
     int low; 
     int high; 

     public SortTask(ArrayList<Integer> inputComp, ArrayList<Integer> temp, int low, int high){ 
      this.inputComp=inputComp; 
      this.temp=temp; 
      this.low=low; 
      this.high=high; 
     } 

     @Override 
     protected void compute(){ 
      if (high-low<SIZE_LIMIT){ 
       insertionSort(inputComp, low, high); 
       return; 
      } 
      int middle = (low + high)/2; 
      invokeAll(new SortTask(inputComp, temp, low, middle), new SortTask(inputComp, temp, middle+1, high)); 
      merge(inputComp, temp, low, middle, high); 
     } 
    } 
     @Override 
     public int compare(Integer c1, Integer c2){ 
     if (c1> c2){ 
      return -1; 
     } 
     if (c1 > c2){ 
      return 1; 
     } 
     return 0; 
    } 

    public static void arrayListCopy(ArrayList<Integer> src, int srcPos, ArrayList<Integer> dest, int destPos, int length){ 
     for (int i = 0; i< length; i++){ 
      dest.set(destPos+i, src.get(srcPos+i)); 
     } 
    } 
    private static void merge(ArrayList<Integer> inputComp1, ArrayList<Integer> inputComp2, int low, int middle, int high){ 
     ThreadedMergeSort sort = new ThreadedMergeSort(); 
     if(sort.compare(inputComp1.get(middle), inputComp1.get(middle+1)) <0){ 
      return; 
     } 
     arrayListCopy(inputComp1, low, inputComp2, low, middle-low+1); 
     int i = low; 
     int j = middle+1; 
     int k = low; 
     while(k < j && j <= high){ 
      if(sort.compare(inputComp2.get(i),inputComp1.get(j)) <= 0){ 
       inputComp1.set(k++, inputComp2.get(i++)); 
      } 
      else{ 
       inputComp1.set(k++,inputComp1.get(j++)); 
      } 
     } 
     arrayListCopy(inputComp2, i, inputComp1, k, j-k); 
    } 

    private static void insertionSort(ArrayList<Integer> inputComp, int low, int high){ 
     ThreadedMergeSort sort = new ThreadedMergeSort(); 
     for(int i = low+1; i<=high; i++){ 
      int j = i; 
      Integer entry = inputComp.get(j); 
      while(low<j && sort.compare(entry, inputComp.get(j-1))< 0){ 
       inputComp.set(j,inputComp.get(j-1)); 
       --j; 
      } 
      inputComp.set(j,entry); 
     } 
    } 
    private static final ForkJoinPool pool = new ForkJoinPool(); 
    private static final int SIZE_LIMIT = 8; 
} 

Answer 1

它在做什麼你問：

ThreadedMergeSort.sort(toSort, 0, toSort.size()-11); 

您的意思是1還是11？