import java.util.Arrays;
import java.util.Random;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;


@SuppressWarnings("serial")
/**
 * An implementation of multi-thread quicksort for int arrays.
 *  
 * Requires Java 7's fork join framework. 
 */
public class ParallelQuicksort extends RecursiveAction {
	
	/**
	 * Main function for timing and testing
	 * @param args unused
	 */
	public static void main(String[] args) { 
		int size = 1000000000;
		//Create a list of random ints 
		int[] sortThis = new int[size];
		System.out.println("Making random list");
		for (int i = 0; i < size; i++) {
			sortThis[i] = random.nextInt();
		}
		
		//do the sort
		System.out.println("Parallel Quicksort started");
		long start = System.currentTimeMillis();
		sort(sortThis);
		long stop = System.currentTimeMillis();
		System.out.println("Parallel Quicksort ended and took: " 
				+ (stop - start) / 1000F + "s");
		
		//check that the list is sorted
		for (int i = 1; i < size; i++) {
			assert sortThis[i - 1] <= sortThis[i];
		}
		System.out.println("Sort confirmed");
		
		//Test Collections.sort  
		System.out.println("Testing java's sequential sort");
		System.out.println("Making random list");
		for (int i = 0; i < size; i++) {
			sortThis[i] = random.nextInt();
		}
		
		System.out.println("Java's sequential sort started");
		start = System.currentTimeMillis();
		Arrays.sort(sortThis);
		stop = System.currentTimeMillis();
		System.out.println("Java's sequential sort ended and took: " 
				+ (stop - start) / 1000F + "s");
	}
	
	/**
	 * Sort an int array using a parallel quicksort 
	 * @param list array to be sorted, in-place
	 */
	public static void sort(int [] list) {				
		ParallelQuicksort myFJQuickSort = new ParallelQuicksort(list, 0, list.length - 1);
		ForkJoinPool pool = new ForkJoinPool();
		pool.invoke(myFJQuickSort);
		pool.shutdown();			
	}
	
	private static final Random random = new Random(1);
	private final static int _sThreshold = 20; //When to switch to insertion 
	private final int[] _list;
	private final int _l;
	private final int _r;
	
	public ParallelQuicksort(int[] list, int l, int r) {
		_list = list;
		_l = l;
		_r = r;
	}

	@Override
	protected void compute() {
		int len = _r - _l + 1;
		if (len <= _sThreshold) { //recursion base case
			//For small n an insertion sort is faster than QS
			insertion(_list,_l,_r);
			return;
		}
		//select a random pivot point
		int p = _l + random.nextInt(len - 1);
		int pValue = _list[p];
		swap(_list, p, _r); //move pivot value to end of the list
		int swapPos = _l;
		for (int i = _l; i < _r; i++) { //walk the list
			if (_list[i] < pValue) {	//move values < pivot value to the 
				swap(_list, i, swapPos);//front of the list
				swapPos++;
			}
		}
		swap(_list, _r, swapPos); //move pivot value back to original spot
		
		//recurse twice; once on list containing values < pivot and once on values >= pivot 
		invokeAll(
				new ParallelQuicksort(_list, _l, swapPos - 1),
				new ParallelQuicksort(_list, swapPos + 1, _r));
	}

	private static void swap(int[] list, int i1, int i2) {
		int temp = list[i1];
		list[i1] = list[i2];
		list[i2] = temp;
	}
	
	public static void insertion(int[] list, int l, int r) {

		for (int i = l + 1; i <= r; i++) { //walk the list

			int insertPos = i;
			int li = list[i];
			//find where this number goes in the sorted list
			while (insertPos > l && li < list[insertPos - 1]) {
				insertPos--;
			}
			//copy everything up one spot
			System.arraycopy(
					list, insertPos, 
					list, insertPos + 1, 
					i - insertPos);
			list[insertPos] = li; //put this value int correct spot
		}
	}
}