uni/inf2440/hw1/Parallel.java

import java.util.Random;
import java.util.Arrays;

class Parallel implements A2Solver {

	class Worker implements Runnable {
		int[] a; // Shared, mutate a[min] to a[max - 1]
		int k;
		int min; // Inclusive
		int max; // Exclusive

		Worker(int[] a, int k, int min, int max) {
			this.a = a;
			this.k = k;
			this.min = min;
			this.max = max;
		}

		public void run() {
			Util.insertionSortReverse(a, min, min + k);

			// Insert the biggest values in a[k..n] into a[0..k-1]
			for (int i = min + k; i < max; ++i) {
				Util.insertAt(a, min, k, i);
			}
		}
	}

	public void solveA2(int[] a, int k) {

		// Set up workers and start threads
		int nthreads = Runtime.getRuntime().availableProcessors();
		Worker[] workers = new Worker[nthreads];
		Thread[] threads = new Thread[nthreads];
		int prev = 0;
		int step = (a.length / nthreads) + 1;
		for (int i = 0; i < nthreads; ++i) {
			Worker w = new Worker(
				a, k, prev, Math.min(prev + step, a.length - 1));
			workers[i] = w;

			Thread t = new Thread(w);
			threads[i] = t;

			t.start();

			prev += step;
		}

		// Wait for workers to complete
		for (Thread t: threads) {
			try {
				t.join();
			} catch (InterruptedException ex) {}
		}

		// Merge
		for (int wi = 1; wi < nthreads; ++wi) {
			Worker w = workers[wi];
			for (int i = 0; i < k; ++i) {
				if (a[w.min + i] > a[k - 1])
					Util.insertAt(a, 0, k, w.min + i);
			}
		}
	}
}