package com.andreimosso.util;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.List;

/**
 * @author Andrei Mosso Mendoza
 * @version 1.0
 */
public class DualSort {

	private static final int SINGLE_THREAD_SORT_THRESHOLD = 1000;
	
	private DualSort() {}
	
	public static <T extends Comparable<? super T>> void sort(final List<T> list) {
	
		T arr1[] = (T[])Array.newInstance(Comparable.class, list.size());
		final T arr[] = list.toArray(arr1);
		
		if (list.size() > SINGLE_THREAD_SORT_THRESHOLD) {
			// Usado para bloquear el flujo mientras los hilos corren.
			final Thread timer = new Thread() {
				
				public void run() {
				
					try {
						Thread.sleep(1000000000000000L);
					}
					catch (InterruptedException ie) {}
				}
			};
			timer.start();
			
			final boolean finished[] = new boolean[2];
			final int cuts[] = {0, arr.length / 2, arr.length};
			
			new Thread() {
			
				public void run() {
				
					// Ordenamos la primera sección del arreglo.
					Arrays.sort(arr, cuts[0], cuts[1]);
					// Al terminar, cada hilo marca su bandera.
					finished[0] = true;
					
					// Revisamos que todos los hilos hayan terminado.
					if (!finished[0] || !finished[1]) {
						return;
					}
					
					merge(arr, cuts);
					for (int j = 0; j < arr.length; j++) {
						list.set(j, (T)arr[j]);
					}
					
					timer.interrupt();
				}
			}.start();
			
			new Thread() {
			
				public void run() {
				
					// Ordenamos la segunda sección del arreglo.
					Arrays.sort(arr, cuts[1], cuts[2]);
					// Al terminar, cada hilo marca su bandera.
					finished[1] = true;
					
					// Revisamos que todos los hilos hayan terminado.
					if (!finished[0] || !finished[1]) {
						return;
					}
					
					merge(arr, cuts);
					
					for (int j = 0; j < arr.length; j++) {
						list.set(j, (T)arr[j]);
					}
					timer.interrupt();
				}
			}.start();
			
			try {
				timer.join();
			}
			catch (InterruptedException ie) {}
		}
		else {
			Arrays.sort(arr);
			
			for (int j = 0; j < arr.length; j++) {
				list.set(j, (T)arr[j]);
			}
		}
	}
	
	private static <T extends Comparable<? super T>> void merge(T arr[], int cuts[]) {
	
		int index1 = cuts[0];
		int index2 = cuts[1];
		T src[] = arr.clone();
		
		for (int i = 0; i < src.length; i++) {
			if (index1 >= cuts[1]) {
				arr[i] = src[index2++];
			}
			else if (index2 >= cuts[2]) {
				arr[i] = src[index1++];
			}
			else {
				if (src[index1].compareTo(src[index2]) < 0) {
					arr[i] = src[index1++];
				}
				else {
					arr[i] = src[index2++];
				}
			}
		}
	}
}