title: Java - ForkJoin /MergeSort Stackoverflow
body: <p>I'm using the ForkJoin framework to implement a merge sort / insertion sort sorting solution. However I'm getting a stackoverflow error, and can't seem to trace where the issue is occurring. The solution is meant to to sort a rangle of random value from 1 - 10,000000. For range from 0 - 100 i use insertion sort, for ranges greater i use merge sort.</p>
  
  <p>Main Method:</p>
  
  <pre><code>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&lt;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&lt;d.length-1;i++) {
          if(d[i] &gt; d[i+1]) {
              sorted = false;
          }
      }
      System.out.println("Sorted List: "+sorted);
     }
   }
  </code></pre>
  
  <p>Sorting Solution:</p>
  
  <pre><code>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 &lt;= 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 &lt; 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&lt;=q&lt;=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 &lt; q &amp;&amp; j &lt; r){
              if(f[i] &lt;= f[j]){
                  temp[t]=f[i];i++;t++;
              }
              else{
                  temp[t] = f[j]; j++; t++;
              }
          }
          //tag on remaining sequence
          while(i &lt; q){ temp[t]=f[i];i++;t++;}
          while(j &lt; r){ temp[t] = f[j]; j++; t++;}
          //copy temp back to f
          i = p; t = 0;
          while(t &lt; temp.length){ f[i] = temp[t]; i++; t++;}
    }
  
  
   static void insertionSort(int f[], int lb, int ub) {
      for(int i = lb; i&lt; ub; i++) {
          int j = i;
          int k = f[i];
          while((j&gt;0)&amp;&amp;(f[j-1] &gt; k)) {
              f[j] = f[j-1];
              j--;
          }
          f[j] = k;
      }
  }
  
  
  }
  </code></pre>
  
  <p>Stack Trace:</p>
  
  <pre><code>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)
  </code></pre>