Fork Join неправильно сортирует

Question

Я пытаюсь сделать адаптацию сортировки слиянием, используя соединение вилки. Я использую это как пример разветвления / соединения, поэтому мне нужно, чтобы он был базовым. Я хочу отредактировать обычную сортировку слиянием так, чтобы, когда размер сегмента опускался ниже 101 (100 или меньше), он использовал сортировку вставкой для сортировки этого сегмента, а затем выходил из рекурсивного вызова и начинал объединять сегменты вместе. Сортировка просто не работает. Если я изменяю порядок вызова и соединения (чтобы не запускать другой код), он работает нормально, поэтому я предполагаю, что это происходит из-за того, что мои сортировки работают одновременно, что это не правильно. Например, если я напишу int mid = (lb+ub)/2; MergeInsertSortQ left = new MergeInsertSortQ(f,lb,mid); MergeInsertSortQ right = new MergeInsertSortQ(f,mid,ub); left.fork(); left.join(); right.fork(); right.join(); слияния (F, фунт, середина, UB); Это нормально, но по сути это последовательно, поэтому я не пытаюсь это сделать.

Вот код, который я использую (включая небольшой тест в основном)

импорт java.util.concurrent.*;

открытый класс MergeInsertSortQ extends RecursiveAction {

private int[] f;
private int lb, ub;
public MergeInsertSortQ(int f[], int lb, int ub)
{
    this.f = f;
    this.lb=lb;
    this.ub=ub;
}

protected void compute(){
    //Insertion Sort performed when a segment of size
    //100 or less is reached otherwise do merge sort
    if(ub-lb>100)
    {
        int mid = (lb+ub)/2;
        MergeInsertSortQ left = new MergeInsertSortQ(f,lb,mid);
        MergeInsertSortQ right = new MergeInsertSortQ(f,mid,ub);
        invokeAll(left,right);
        left.join();
        right.join();
        merge(f,lb,mid,ub);
    }
    else if(ub-lb>=1)
    {
        for (int i = lb; i<ub;i++)
        {
            int temp = f[i];
            int j = i-1;
            while (j >= 0 && f[j] > temp)
            {
                f[j+1] = f[j];
                j = j-1;
            }
            f[j+1] = temp;
        }
    }
}

protected void merge(int f[], int lower, int middle, int top){
    int i = lower; int j = middle;

    //use temp array to store merged sub-sequence
    int temp[] = new int[top-lower]; int t = 0;

    while(i < middle && j < top)
    {
        if(f[i] <= f[j])
        {
            temp[t]=f[i];i++;t++;
        }
        else{
            temp[t] = f[j]; j++; t++;
        }
    }

    //tag on remaining sequence
    while(i < middle)
    {
        temp[t]=f[i]; i++; t++;
    }
    while(j < top)
    {
        temp[t] = f[j]; j++; t++;
    }

    //copy temp back to f
    i = lower; t = 0;
    while(t < temp.length)
    {
        f[i] = temp[t]; i++; t++;
    }
}

public static void main(String[] args)
{
    //Initialise & print array before sorting
    int A[]=new int[200];
    for(int j=0;j<A.length;j++)
    {
        A[j]=(int)(Math.random()*10000);
        System.out.print(A[j]+" ");
    }
    System.out.println();
    System.out.println("**********************************");
    System.out.println();

    // Do the sort
    ForkJoinPool fjPool=new ForkJoinPool();
    fjPool.invoke(new MergeInsertSortQ(A,0,A.length));

    //Check if array sorted and print
    boolean sorted=true;
    for(int i=0;i<A.length-1;i++)
    {
        System.out.print(A[i] + " ");
        if (A[i]>A[i+1])
        {
            System.out.println();
            System.out.println(A[i]+" is greater than "+A[i+1]+", location "+i);
            sorted=false;
            //break;
        }
    }
    System.out.println();
    if (sorted) System.out.println("The array is sorted!!!");
    else System.out.println("WARNING: The array is NOT SORTED");
}

}