package com.data.struct;

import java.util.concurrent.CountDownLatch;

public class CopyOfMultiThreadMergeSort2 {
  private static void mergeSort(int [] source,int left,int right,CountDownLatch cdl){
    if(left==right){
      cdl.countDown();
      cdl.countDown();
      return ;
    }else{
      int middle=(left+right)/2;
      MergeSortThread t1=new MergeSortThread(source,left,middle,cdl);
      t1.start();
      MergeSortThread t2=new MergeSortThread(source,middle+1,right,cdl);
      t2.start();
      try {
        cdl.await();
      } catch (InterruptedException e) {
        
      }
      
      int[]tmp=new int[right-left+1];
      int l=0;
      int lindex=left;
      int rindex=middle+1;
      for(;lindex<=middle;){
        if(rindex>right){
          break;
        }
        if(source[lindex]<source[rindex]){
          tmp[l++]=source[lindex];
          lindex++;
        }else{
          tmp[l++]=source[rindex];
          rindex++;
        }
      }
      if(lindex==middle+1&&rindex<=right){
        for(;rindex<=right;rindex++){
          tmp[l++]=source[rindex];
        }
      }
      if(rindex>right&&lindex<=middle){
        for(;lindex<=middle;lindex++){
          tmp[l++]=source[lindex];
        }
      }
      
      l=0;
      for(int x=left;x<=right;x++){
        source[x]=tmp[l++];
      }
      
      for(int i=0;i<source.length;i++){
        System.out.print(source[i]+" ");
      }
      System.out.println();
      
    }
    
  }
  
  private static class MergeSortThread extends Thread{
    private int[]A;
    private int p;
    private int r;
    private CountDownLatch cdl;
    public MergeSortThread(int[]A,int p,int r,CountDownLatch cdl){
      this.A=A;
      this.p=p;
      this.r=r;
      this.cdl=cdl;
    }
    @Override
    public void run() {
      CountDownLatch c=new CountDownLatch(2);
      mergeSort(A,p,r,c);
      try {
        c.await();
      } catch (InterruptedException e) {
        e.printStackTrace();
      }
      
      this.cdl.countDown();
    }
    
    
  }
  public static void main(String[] args) {
    int[] data=new int[]{4,5,2,9,1,0,7};
    for(int i=0;i<data.length;i++){
      System.out.print(data[i]+" ");
    }
    System.out.println();
    CountDownLatch cd=new CountDownLatch(2);
    mergeSort(data,0,data.length-1,cd);;
    try {
      cd.await();
    } catch (InterruptedException e) {
      e.printStackTrace();
    }
    for(int i=0;i<data.length;i++){
      System.out.print(data[i]+" ");
    }
    System.out.println();

  }

}