Java - ForkJoin/MergeSort Stackoverflow

Question

Я использую фреймворк ForkJoin для реализации сортировки сортировки/вставки сортировки слияния. Однако я получаю ошибку stackoverflow и не могу проследить, где происходит проблема. Решение предназначено для сортировки звонка случайного значения от 1 до 10 000 000. Для диапазона от 0 до 100 я использую сортировку вставки, для диапазонов больше я использую сортировку слияния.

Основной метод:

class Assignment3 { 
    public static void main(String[] args) {    
    long startTime1 = System.currentTimeMillis(); 
    int S = 10000000; 
    int d[] = new int[S]; 

    for(int j=0;j<d.length;j++) { 
     d[j] = (int)(Math.random()*10000); 
    } 

    ForkJoinPool fjpool = new ForkJoinPool(); 
    // Array, lb, ub 
    fjpool.invoke(new Ass3Q2(d,0,d.length)); 

    long endTime1 = System.currentTimeMillis(); 
    long runningTime1 = endTime1 - startTime1; 
    System.out.println(runningTime1+" millisecs ("+(runningTime1/1000.0)+")"); 

    boolean sorted = true; 
    for(int i=0;i<d.length-1;i++) { 
     if(d[i] > d[i+1]) { 
      sorted = false; 
     } 
    } 
    System.out.println("Sorted List: "+sorted); 
    } 
} 

Сортировка Решение:

class Ass3Q2 extends RecursiveAction{ 

/* RecursiveAction becasue we dont want to return a value */ 

private int[] f; 
private int lb; 
private int ub; 
private static final int BLOCKSIZE = 100; 

public Ass3Q2(int a[], int l, int u) { 
    f = a;lb = l;ub = u; 
} 

protected void compute() { 
    // Check if bounds are within block size 
    if(ub-lb <= BLOCKSIZE) { 
     // Do Insertion sort 
     System.out.println("UB/LB: "+(ub-lb)); 
     insertionSort(f, lb, ub); 
    } else { 
     // MergeSort 
     int m = lb + (ub-lb)/2; 
     System.out.println("Mid: "+m); 
     Ass3Q2 left = new Ass3Q2(f, lb, m); 
     Ass3Q2 right = new Ass3Q2(f, m+1, ub); 
     invokeAll(left,right); 
     left.join();right.join(); 
     mergeSort(f, lb, ub); 
    } 
} 

static void mergeSort(int a[], int l, int u) { 
    if(l+1 < u) { 
     int mid = (l+u)/2; 
     mergeSort(a,l,u); 
     mergeSort(a,mid,u); 
     merge(a,l,mid,u); 
    } 
} 

static void merge(int f[], int p, int q, int r){ 
     //p<=q<=r 
     int i = p; int j = q; 
     //use temp array to store merged sub-sequence 
     int temp[] = new int[r-p]; int t = 0; 
     while(i < q && j < r){ 
      if(f[i] <= f[j]){ 
       temp[t]=f[i];i++;t++; 
      } 
      else{ 
       temp[t] = f[j]; j++; t++; 
      } 
     } 
     //tag on remaining sequence 
     while(i < q){ temp[t]=f[i];i++;t++;} 
     while(j < r){ temp[t] = f[j]; j++; t++;} 
     //copy temp back to f 
     i = p; t = 0; 
     while(t < temp.length){ f[i] = temp[t]; i++; t++;} 
    } 


static void insertionSort(int f[], int lb, int ub) { 
    for(int i = lb; i< ub; i++) { 
     int j = i; 
     int k = f[i]; 
     while((j>0)&&(f[j-1] > k)) { 
      f[j] = f[j-1]; 
      j--; 
     } 
     f[j] = k; 
    } 
} 


} 

Трассировка стека:

Exception in thread "main" java.lang.StackOverflowError 
at sun.reflect.NativeConstructorAccessorImpl.newInstance0(Native Method) 
at sun.reflect.NativeConstructorAccessorImpl.newInstance(Unknown Source) 
at sun.reflect.DelegatingConstructorAccessorImpl.newInstance(Unknown Source) 
at java.lang.reflect.Constructor.newInstance(Unknown Source) 
at java.util.concurrent.ForkJoinTask.getThrowableException(Unknown Source) 
at java.util.concurrent.ForkJoinTask.reportResult(Unknown Source) 
at java.util.concurrent.ForkJoinTask.join(Unknown Source) 
at java.util.concurrent.ForkJoinPool.invoke(Unknown Source) 
at Assignment3.main(Assignment3.java:71) 
Caused by: java.lang.StackOverflowError 
at Ass3Q2.mergeSort(Assignment3.java:150) 
at Ass3Q2.mergeSort(Assignment3.java:150) 
at Ass3Q2.mergeSort(Assignment3.java:150) 
at Ass3Q2.mergeSort(Assignment3.java:150) 
at Ass3Q2.mergeSort(Assignment3.java:150) 
at Ass3Q2.mergeSort(Assignment3.java:150) 

Answer 1

mergeSort называет себя с теми же параметрами: mergeSort(a,l,u); (если мы входим в if) , в этом причина stackoverflow er ROR.

static void mergeSort(int a[], int l, int u) { 
    if(l+1 < u) { 
     int mid = (l+u)/2; 
     mergeSort(a,l,u); // this call is most likely unwanted 
     mergeSort(a,mid,u); 
     merge(a,l,mid,u); 
    } 
}