package op1_concurrency;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class RecursiveSort {
	private Random rng = new Random();

	public static void main(String[] args) {
		RecursiveSort op3 = new RecursiveSort();
		ArrayList<Integer> list = op3.randomlist(0, 64);
		// ArrayList<Integer> list2 = randomlist(0, 50000);
		// ArrayList<Integer> list3 = randomlist(0, 100000);
		// ArrayList<Integer> list4 = randomlist(0, 200000);
		// ArrayList<Integer> list5 = randomlist(0, 400000);
		// ArrayList<Integer> list6 = randomlist(0, 800000);
		// System.out.println(testtijd(list));
		// System.out.println(testtijd(list2));
		// System.out.println(testtijd(list3));
		// System.out.println(testtijd(list4));
		// System.out.println(testtijd(list5));
		// System.out.println(testtijd(list6));

		System.out.println(op3.recursiveSort(list).toString());

	}

	protected static List<Integer> recursiveSort(List<Integer> recursivelist) {


		if (recursivelist.size() <= 2) {
			return sortGivenArray(recursivelist);
		} else {
			int size = recursivelist.size() /2;
			List<Integer> sublist = (List<Integer>)recursivelist.subList(0, size);
			List<Integer> sublist2 =  recursivelist.subList(size, recursivelist.size());



			Runnable r1 = new Thread(){

				public void run() {
					recursiveSort(sublist);
				}
			};
			Thread t1 = new Thread(r1);
			t1.start();



			Runnable r2 = new Thread(){

				public void run() {
					recursiveSort(sublist2);
				}
			};
			Thread t2 = new Thread(r2);
			t2.start();

			try {
				t1.join();
				t2.join();

			} catch (InterruptedException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			System.out.println("merge");
			System.out.println(sublist.toString());
			return merge(sublist, sublist2);
		}
	}

	private static List<Integer> merge(List<Integer> left, List<Integer> right) {
		List<Integer> whole = new List<Integer>();
		int leftIndex = 0;
		int rightIndex = 0;
		int wholeIndex = 0;

		// As long as neither the left nor the right arraylist has
		// been used up, keep taking the smaller of left.get(leftIndex)
		// or right.get(rightIndex) and adding it at both.get(bothIndex).
		while (leftIndex < left.size() && rightIndex < right.size()) {
			if ((left.get(leftIndex).compareTo(right.get(rightIndex))) < 0) {
				whole.add(left.get(leftIndex));
				leftIndex++;
			} else {
				whole.add(right.get(rightIndex));
				rightIndex++;
			}
			wholeIndex++;
		}

		List<Integer> rest;
		int restIndex = 0;
		if (leftIndex >= left.size()) {
			// The left arraylist has been use up...
			rest = right;
			restIndex = rightIndex;
		} else {
			// The right arraylist has been used up...
			rest = left;
			restIndex = leftIndex;
		}

		// Copy the rest of whichever arraylist (left or right) was
		// not used up.
		for (int i = restIndex; i < rest.size(); i++) {
			whole.add(rest.get(i));
			wholeIndex++;
		}
		return whole;
	}

	public ArrayList<Integer> randomlist(int min, int max) {
		ArrayList<Integer> list = new ArrayList<Integer>();

		for (int i = 0; i < max; i++) {
			list.add(rng.nextInt(max - min) + min);
		}
		return list;
	}

	public long testtijd(ArrayList<Integer> array) {
		long before = System.currentTimeMillis();
		sortGivenArray(array);
		long after = System.currentTimeMillis();
		return after - before;
	}

	public static List<Integer> sortGivenArray(List<Integer> inputArray) {
		for (int i = 1; i < inputArray.size(); i++) {

			int key = inputArray.get(i);

			for (int j = i - 1; j >= 0; j--) {
				if (key < inputArray.get(j)) {
					// Shifting Each Element to its right as key is less than
					// the existing element at current index
					inputArray.set(j + 1, inputArray.get(j));

					// Special case scenario when all elements are less than
					// key, so placing key value at 0th Position
					if (j == 0) {
						inputArray.set(0, key);
					}
				} else {
					// Putting Key value after element at current index as Key
					// value is no more less than the existing element at
					// current index
					inputArray.set(j + 1, key);
					break; // You need to break the loop to save un necessary
							// iteration
				}
			}
		}
		return inputArray;
	}

}