Java Question:

Your task is to implement a parallel sorting algorithm such that each partition of the array is sorted in parallel. You should consider two different schemes for deciding whether to sort in parallel.

A cutoff (defaults to, say, 1000) which you will update according to the first argument in the command line when running. It's your job to experiment and come up with a good value for this cutoff. If there are fewer elements to sort than the cutoff, then you should use the system sort instead.

Recursion depth or number of available threads. Using this determination, you might decide on an ideal number (t) of separate threads (stick to powers of 2) and arrange for that number of partitions to be parallelized (by preventing recursion after depth of lg t is reached).

The Main class can be used as is but the ParSort class needs to be implemented where you see "TODO..."

Main class:

import java.util.Random;
	public class Main {
	public static void main(String[] args) {
	if (args.length>0) ParSort.cutoff = Integer.parseInt(args[0]);
	Random random = new Random(0L);
	int[] array = new int[2000];
	for (int i = 0; i < array.length; i++) array[i] = random.nextInt(10000);
	ParSort.sort(array, 0, array.length);
	//for (int i : array) System.out.println(i);
	if (array[0]==11) System.out.println("Success!");
	}
	}

ParSort class:

import java.util.Arrays;
	import java.util.concurrent.CompletableFuture;
	class ParSort {
	public static int cutoff = 1000;
	public static void sort(int[] array, int from, int to) {
	int size = to - from;
	if (size < cutoff) Arrays.sort(array, from, to);
	else {
	CompletableFuture parsort1 = null; // TODO implement me
	CompletableFuture parsort2 = null; // TODO implement me
	CompletableFuture parsort = parsort1.
	thenCombine(parsort2, (xs1, xs2) -> {
	int[] result = new int[xs1.length + xs2.length];
	// TODO implement me
	return result;
	});
	parsort.whenComplete((result, throwable) -> {}); // TODO implement me
	parsort.join();
	}
	}
	private static CompletableFuture parsort(int[] array, int from, int to) {
	return CompletableFuture.supplyAsync(
	() -> {
	int[] result = new int[to - from];
	// TODO implement me
	return result;
	}
	);
	}
	}