//  Copyright 2016 The Sawdust Open Source Project
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//

package sort;

import array.Common;

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

import static array.Common.divide;

public class MergeSortRecursionMultiThreads3 {
    public static <T extends Comparable<T>> void mergeSort(T[] arr) {
        ForkJoinPool forkJoinPool = new ForkJoinPool(Runtime.getRuntime().availableProcessors());
        forkJoinPool.invoke(new DivideMergeInSortAction(arr));
    }
}

/**
 * <pre>
 * Should use RecursiveTask.
 * --But as the input is array and only its content is changed in the precess of fork.
 * So use RecursiveAction to make it simple.
 *
 * --Must join() to wait else the result will be unexpected
 *
 * invokeAll(l,r); // same as l.fork();  r.fork(); l.join();  r.join();
 */
class DivideMergeInSortAction extends RecursiveAction {
    private final Comparable[] arr;

    @Override
    protected void compute() {
        // Input check, threshold
        if (arr == null || arr.length <= 1) {
            return;
        }
        // 1 Divide into 2 halves
        final Comparable[][] halves = divide(arr);

        // 2 Divide, merge each halves in sort
        RecursiveAction l = new DivideMergeInSortAction(halves[0]);
        RecursiveAction r = new DivideMergeInSortAction(halves[1]);
        invokeAll(l, r);

        // 3 Merge them back into one.
        Common.mergeInsort(halves[0], halves[1], arr);
    }

    public DivideMergeInSortAction(Comparable[] arr) {
        this.arr = arr;
    }
}

@@ -822,257 +822,29 @@
     
-public static %3CT extends Comparable%3CT%3E%3E void mergeSort(T%5B%5D arr) %7B%0A        ForkJoinPool forkJoinPool = new ForkJoinPool(Runtime.getRuntime().availableProcessors());%0A        forkJoinPool.invoke(new DivideMergeInSortAction(arr));%0A    %7D%0A%7D%0A%0A/**%0A * %3Cpre%3E%0A
+/**%0A     * %3Cpre%3E%0A    
  * S
@@ -868,16 +868,20 @@
 veTask.%0A
+    
  * --But
@@ -960,17 +960,23 @@
  fork.%0A 
-*
+    *  
  So use 
@@ -1011,18 +1011,26 @@
 imple.%0A 
-*%0A
+    *%0A    
  * --Mus
@@ -1082,18 +1082,26 @@
 pected%0A 
-*%0A
+    *%0A    
  * invok
@@ -1169,11 +1169,34 @@
 );%0A 
-*/%0A
+    */%0A    private static 
 clas
@@ -1247,16 +1247,20 @@
 ction %7B%0A
+    
     priv
@@ -1263,22 +1263,16 @@
 private 
-final 
 Comparab
@@ -1282,16 +1282,20 @@
 %5D arr;%0A%0A
+    
     @Ove
@@ -1304,16 +1304,20 @@
 ide%0A    
+ 
+   
 protecte
@@ -1343,16 +1343,20 @@
         
+   
+ 
 // Input
@@ -1373,16 +1373,20 @@
 reshold%0A
+    
         
@@ -1435,16 +1435,20 @@
         
+    
 return;%0A
@@ -1459,52 +1459,27 @@
     
-%7D%0A
     
+%7D%0A%0A
     
-// 1 Divide into 2 halves%0A
+   
      
-   
 fina
@@ -1528,57 +1528,14 @@
     
-  // 2 Divide, merge each halves in sort%0A
       
-  
 Recu
@@ -1586,24 +1586,28 @@
 halves%5B0%5D);%0A
+    
         Recu
@@ -1670,16 +1670,20 @@
         
+    
 invokeAl
@@ -1701,50 +1701,15 @@
     
- 
-  // 3 Merge them back into one.%0A
        
- 
 Comm
@@ -1751,16 +1751,20 @@
 , arr);%0A
+    
     %7D%0A%0A 
@@ -1766,16 +1766,20 @@
  %7D%0A%0A    
+ 
+   
 public D
@@ -1829,16 +1829,20 @@
         
+  
+  
 this.arr
@@ -1849,16 +1849,264 @@
  = arr;%0A
+        %7D%0A    %7D%0A%0A    public static %3CT extends Comparable%3CT%3E%3E void mergeSort(T%5B%5D arr) %7B%0A        ForkJoinPool forkJoinPool = new ForkJoinPool(Runtime.getRuntime().availableProcessors());%0A        forkJoinPool.invoke(new DivideMergeInSortAction(arr));%0A
     %7D%0A%7D%0A

Make DivideMergeInSort as inner class of MergeSortRecursionMultiThreads3