public class BuggyMTMergeSort {

	private int[] to_sort;
	private int total_sort_threads;

	public BuggyMTMergeSort(int[] to_sort, int no_threads) {
		this.to_sort = to_sort;
		this.total_sort_threads= no_threads;
	}

	public void sort() {
		// correct amount of threads, if it is invalid
		if (to_sort.length<total_sort_threads) {
			total_sort_threads = to_sort.length;
		} else if (total_sort_threads<1) {
			total_sort_threads = 1;
		}

		// instantiate the ThreadSorts to sort tha array and start them
		ParallelSort[] list = new ParallelSort[total_sort_threads];
		for (int i=0;i<total_sort_threads;i++) {
			ParallelSort sorter = new ParallelSort(i);
			list[i] = sorter;
			sorter.start();
		}

		// Wait until all ThreadSorts have finished their work
		for (int i=0;i<total_sort_threads;i++) {
			try {
				list[i].join();
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
		}

		// Collect all arrays
		int[][] arrays = new int[total_sort_threads][];
		for (int i=0;i<total_sort_threads;i++) {
			arrays[i] = list[i].getArray();
		}

		// merge the sorted arrays together
		while(arrays.length>1) {
			int n = arrays.length;
			int[][] temp = new int[(n+1)/2][]; // to store the merged arrays
			temp[(n+1)/2-1] = arrays[n-1]; // to not lose the last part, if there is an odd amount of parts
			for (int i=0;i<n/2;i++) {
				temp[i] = merge(arrays[2*i], arrays[2*i+1]);
			}
			arrays = temp;
		}

		// copy the sorted array into the to_sort reference
		System.arraycopy(arrays[0], 0, to_sort, 0, arrays[0].length);
	}

	/**
	 * Merge two arrays together
	 */
	private int[] merge(int[] a, int[] b) {
		int na = a.length;
		int nb = b.length;
		int ia, ib; // pointers to the arrays
		int[] array = new int[na+nb];
		for (ia = 0, ib = 0; ia<na && ib<nb; ) {
			if (a[ia]<=b[ib]) {
				array[ia+ib] = a[ia];
				ia++;
			} else {
				array[ia+ib] = b[ib];
				ib++;
			}
		}

		// append the remaining elements into the array
		System.arraycopy(a, ia, array, ia+ib, na-ia);
		System.arraycopy(b, ib, array, na+ib, nb-ib);

		return array;
	}

	private class ParallelSort extends Thread {
		private int index;
		private int[] array;

		private ParallelSort(int index) {
			this.index = index;
		}

		@Override
		public void run() {
			// extract your part of elements to sort
			int n = to_sort.length;
			int m = total_sort_threads;
			int start = index*n/m;
			int end =  (index+1)*n/m;
			this.array = new int[end - start];
			System.arraycopy(to_sort, start, array, 0, end-start);
			BuggySeqMergeSort sorter = new BuggySeqMergeSort(array);

			sorter.sort();
		}

		private int[] getArray() {
			return array;
		}
	}
}