package RandomizedSelect;

import java.util.LinkedList;

public class ParallelMergeSort {
	static void mergeSort(int[] A){
		mergeSort(A, 0, A.length-1);
	}
	static void mergeSort(int[] A, int low, int high){
		if(high - low < 1){
			return;
		}else{
			int pivot = Math.floorDiv(high + low, 2);
			Thread proc = new Thread(new Runnable(){
				@Override
				public void run(){
					mergeSort(A, low, pivot);
					mergeSort(A, pivot + 1, high);
				}
			});
			proc.start();
			while(proc.isAlive());
			merge(A, low, pivot, pivot+1, high);
		}
	}
	static void merge(int[] a, int l1, int r1, int l2, int r2) {
		LinkedList<Integer> list = new LinkedList<Integer>();
		for(int i = l1; i <= r1; i++){
			list.add(a[i]);
		}
		int index = 0;
		for(int i = l2; i <= r2; i++){
			while(index < list.size() && list.get(index) < a[i]) index++;
			list.add(index, a[i]);
		}
		for(int i = 0; i < list.size(); i++){
			a[i + l1] = list.get(i);
		}
	}
	public static void main(String[] args){
		int[] array = {1,5,12,15,12,11,3, 16, 2, 5, 18};
		mergeSort(array);
		for(int i: array){
			System.out.print(i + " ");
		}
	}
}