/*
 * QuickSort.java -- Multithreaded quick sort with a task bag
 */

import java.util.concurrent.Executor;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

class QuickSortTask implements Runnable {
    double data[];
    int base;
    int n;
    QuickSort manager;
    public QuickSortTask( double data[], int base, int n,
			  QuickSort manager )
    {
	this.data    = data ;
	this.base    = base ;
	this.n       = n ;
	this.manager = manager ;
    }
    static final int SORT_DIRECT = 200;
    public void run() 
    {
	int i,j;
	if( n <= SORT_DIRECT )
	{
	    for( j=1; j<n; j++)
	    {
		double key = data[base+j];
		for( i=j-1; i >= 0 && key < data[base+i]; i--)
		    data[base+i+1] = data[base+i];
		data[base+i+1] = key;
	    }
	    manager.task_done();
	    return;
	}
	i = 0;
	j = n - 1;
	while( true )
	{
	    while( data[base+i] < data[base+j] ) j--;
	    if( i >= j ) break;
	    {  double t = data[base+i]; data[base+i] = data[base+j]; 
	       data[base+j] = t;  } /* swap */
	    i++;
	    while( data[base+i] < data[base+j] ) i++;
	    if (i >= j) { i = j; break; }
	    {  double t = data[base+i]; data[base+i] = data[base+j]; 
	       data[base+j] = t;  } /* swap */
	    j--;
	}
	manager.add_task( data,base,    i     );
	manager.add_task( data,base+i+1,n-i-1 );
	manager.task_done();
    }
}

class QuickSort {
    int task_count;
    ExecutorService exec;
    public QuickSort(int n_threads)
    {
	task_count = 0;
	exec = Executors.newFixedThreadPool(n_threads);
    }
    public synchronized void add_task( double data[], int base, int n )
    {
	task_count ++;
	Runnable task = new QuickSortTask( data,base,n,this );
	exec.execute( task );
    }
    public synchronized void task_done()
    {
	task_count -- ;
	if( task_count <= 0 )
	    notify();
    }
    public synchronized void work_wait()
	throws java.lang.InterruptedException
    {
	while( task_count > 0 )
	{
	    wait();
	}
	exec.shutdown();
    }
}