package cn.piggy;

import java.util.Arrays;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.ForkJoinTask;
import java.util.concurrent.RecursiveTask;

public class MergePiggy {
	
	public static void main(String[] args) throws Exception {
		int []arr = {9,8,7,6,5,4,3,2,1};
		ForkJoinPool forkJoinPool = new ForkJoinPool();
		CountTask countTask = new CountTask(0, arr.length-1, arr);
		ForkJoinTask<int[]> submit = forkJoinPool.submit(countTask);
		System.out.println(Arrays.toString(submit.get()));
	}
	
}


class CountTask extends RecursiveTask<int[]>{

	/**
	 * 
	 */
	private static final long serialVersionUID = 1L;
	
	private int left;
	
	private int right;
	
	private int[] array;

	public CountTask(int left, int right, int[] array) {
		super();
		this.left = left;
		this.right = right;
		this.array = array;
	}

	@Override
	protected int[] compute() {
		if (right - left >= 3) {
			int num = right+left;
			int mid = num/2;
			CountTask one = new CountTask(left, mid, array);
			CountTask two = new CountTask(mid+1, right, array);
			one.fork();
			two.fork();
			int[] join1 = one.join();
			int[] join2 = two.join(); 
			mergePiggy(join1,join2);
		}else {
			int []temp = new int[array.length];
			sort(array,left,right,temp);
		}
		return array;
	}
	
	private int[] mergePiggy(int[] joinOne,int[]joinTwo) {
		int[] arrayTemp = new int[right-left+1];
		int mid = (right+left)/2;
		int k = 0;
		int i = left;
		int j = mid+1;
		while(i<=mid && j<=right) {
			if(joinOne[i]<=joinTwo[j]) {
				arrayTemp[k++] = joinOne[i++];
			}else {
				arrayTemp[k++] = joinTwo[j++];
			}
		}
		while(i<=mid){
			arrayTemp[k++] = joinOne[i++];
        }
		while(j<=right){
			arrayTemp[k++] = joinTwo[j++];
        }
		k = 0;
		for(int z=left; z<=right; z++) {
			array[z] = arrayTemp[k];
			k++;
		}
		return array;
	}
    
    private void sort(int[] arr,int left,int right,int []temp){
        if(left<right){
            int mid = (left+right)/2;
            sort(arr,left,mid,temp);
            sort(arr,mid+1,right,temp);
            merge(arr,left,mid,right,temp);
        }
    }
    
    private void merge(int[] arr,int left,int mid,int right,int[] temp){
        int i = left;
        int j = mid+1;
        int t = 0;
        while (i<=mid && j<=right){
            if(arr[i]<=arr[j]){
                temp[t++] = arr[i++];
            }else {
                temp[t++] = arr[j++];
            }
        }
        while(i<=mid){
            temp[t++] = arr[i++];
        }
        while(j<=right){
            temp[t++] = arr[j++];
        }
        int k = 0;
        //将temp中的元素全部拷贝到原数组中
        while(left <= right){
            arr[left++] = temp[k++];
        }
    }
	
}