-
-
Save egenedy97/1b95f96893fbaca2027e89168e24c09a to your computer and use it in GitHub Desktop.
Merge sort implementation in java using multithreading
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| package assign6; | |
| import java.util.*; | |
| /** | |
| * This class carries out the merge sort algorithm in parallel. | |
| * | |
| * @author Taylor Carr | |
| * @version 1.0 | |
| */ | |
| public class ParallelMergeSorter extends Thread { | |
| /** | |
| * Sorts an array, using the merge sort algorithm. | |
| * | |
| * @param a the array to sort | |
| * @param comp the comparator to compare array elements | |
| */ | |
| public static <E> void sort(E[] a, Comparator<? super E> comp, int threads) { | |
| parallelMergeSort(a, 0, a.length-1, comp, threads); | |
| } | |
| /** | |
| * Sorts a range of an array, using the merge sort algorithm. | |
| * | |
| * @param a the array to sort | |
| * @param from the first index of the range to sort | |
| * @param to the last index of the range to sort | |
| * @param comp the comparator to compare array elements | |
| */ | |
| private static <E> void mergeSort(E[] a, int from, int to, | |
| Comparator<? super E> comp) { | |
| if (from == to) { | |
| return; | |
| } | |
| if (to - from >0) { | |
| int mid = (from + to) / 2; | |
| // Sort the first and the second half | |
| mergeSort(a, from, mid, comp); | |
| mergeSort(a, mid + 1, to, comp); | |
| merge(a, from, mid, to, comp); | |
| } | |
| } | |
| /** | |
| * Takes an array and merge sorts it in parallel if there | |
| * are multiple threads | |
| * | |
| * @param <E> | |
| * @param a is the array to sort | |
| * @param from is the first value to sort | |
| * @param to is the last value to sort | |
| * @param comp is the comparator that checks two numbers | |
| * @param availableThreads is how many threads there are to utilize | |
| */ | |
| private static <E> void parallelMergeSort(E[] a, int from, int to, Comparator<? super E> comp, int availableThreads){ | |
| if (to - from > 0){ | |
| if (availableThreads <=1) { | |
| mergeSort(a, from, to, comp); | |
| } | |
| else { | |
| int middle = to/2; | |
| Thread firstHalf = new Thread(){ | |
| public void run(){ | |
| parallelMergeSort(a, from, middle, comp, availableThreads - 1); | |
| } | |
| }; | |
| Thread secondHalf = new Thread(){ | |
| public void run(){ | |
| parallelMergeSort(a, middle + 1, to, comp, availableThreads - 1); | |
| } | |
| }; | |
| firstHalf.start(); | |
| secondHalf.start(); | |
| try { | |
| firstHalf.join(); | |
| secondHalf.join(); | |
| } catch (InterruptedException ie) { | |
| ie.printStackTrace(); | |
| } | |
| merge(a, from, middle, to, comp); | |
| } | |
| } | |
| } | |
| /** | |
| * Merges two adjacent subranges of an array | |
| * | |
| * @param a the array with entries to be merged | |
| * @param from the index of the first element of the first range | |
| * @param mid the index of the last element of the first range | |
| * @param to the index of the last element of the second range | |
| * @param comp the comparator to compare array elements | |
| */ | |
| @SuppressWarnings("unchecked") | |
| private static <E> void merge(E[] a, | |
| int from, int mid, int to, Comparator<? super E> comp) { | |
| int n = to - from + 1; | |
| // Size of the range to be merged | |
| // Merge both halves into a temporary array b | |
| Object[] b = new Object[n]; | |
| int i1 = from; | |
| // Next element to consider in the first range | |
| int i2 = mid + 1; | |
| // Next element to consider in the second range | |
| int j = 0; | |
| // Next open position in b | |
| // As long as neither i1 nor i2 past the end, move | |
| // the smaller element into b | |
| while (i1 <= mid && i2 <= to) { | |
| if (comp.compare(a[i1], a[i2]) < 0) { | |
| b[j] = a[i1]; | |
| i1++; | |
| } else { | |
| b[j] = a[i2]; | |
| i2++; | |
| } | |
| j++; | |
| } | |
| // Note that only one of the two while loops | |
| // below is executed | |
| // Copy any remaining entries of the first half | |
| while (i1 <= mid) { | |
| b[j] = a[i1]; | |
| i1++; | |
| j++; | |
| } | |
| // Copy any remaining entries of the second half | |
| while (i2 <= to) { | |
| b[j] = a[i2]; | |
| i2++; | |
| j++; | |
| } | |
| // Copy back from the temporary array | |
| for (j = 0; j < n; j++) { | |
| a[from + j] = (E) b[j]; | |
| } | |
| } | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| package assign6; | |
| import java.util.Arrays; | |
| import java.util.Comparator; | |
| import java.util.Random; | |
| /** | |
| * @author Taylor Carr | |
| * @version 1.0 | |
| */ | |
| public class ParallelSortTester { | |
| public static void main(String[] args) { | |
| runSortTester(); | |
| } | |
| /** | |
| * Runs a nested for loop of tests that call ParallelMergeSorter and | |
| * then checks the array afterwards to ensure correct sorting | |
| */ | |
| public static void runSortTester() { | |
| int SIZE = 1000, // initial length of array to sort | |
| ROUNDS = 15, | |
| availableThreads = (Runtime.getRuntime().availableProcessors())*2; | |
| Integer[] a; | |
| Comparator<Integer> comp = new Comparator<Integer>() { | |
| public int compare(Integer d1, Integer d2) { | |
| return d1.compareTo(d2); | |
| } | |
| }; | |
| System.out.printf("\nMax number of threads == %d\n\n", availableThreads); | |
| for (int i = 1; i <= availableThreads; i*=2) { | |
| if (i == 1) { | |
| System.out.printf("%d Thread:\n", i); | |
| } | |
| else { | |
| System.out.printf("%d Threads:\n", i); | |
| } | |
| for (int j = 0, k = SIZE; j < ROUNDS; ++j, k*=2) { | |
| a = createRandomArray(k); | |
| // run the algorithm and time how long it takes to sort the elements | |
| long startTime = System.currentTimeMillis(); | |
| ParallelMergeSorter.sort(a, comp, availableThreads); | |
| long endTime = System.currentTimeMillis(); | |
| if (!isSorted(a, comp)) { | |
| throw new RuntimeException("not sorted afterward: " + Arrays.toString(a)); | |
| } | |
| System.out.printf("%10d elements => %6d ms \n", k, endTime - startTime); | |
| } | |
| System.out.print("\n"); | |
| } | |
| } | |
| /** | |
| * Returns true if the given array is in sorted ascending order. | |
| * | |
| * @param a the array to examine | |
| * @param comp the comparator to compare array elements | |
| * @return true if the given array is sorted, false otherwise | |
| */ | |
| public static <E> boolean isSorted(E[] a, Comparator<? super E> comp) { | |
| for (int i = 0; i < a.length - 1; i++) { | |
| if (comp.compare(a[i], a[i + 1]) > 0) { | |
| System.out.println(a[i] + " > " + a[i + 1]); | |
| return false; | |
| } | |
| } | |
| return true; | |
| } | |
| // Randomly rearranges the elements of the given array. | |
| public static <E> void shuffle(E[] a) { | |
| for (int i = 0; i < a.length; i++) { | |
| // move element i to a random index in [i .. length-1] | |
| int randomIndex = (int) (Math.random() * a.length - i); | |
| swap(a, i, i + randomIndex); | |
| } | |
| } | |
| // Swaps the values at the two given indexes in the given array. | |
| public static final <E> void swap(E[] a, int i, int j) { | |
| if (i != j) { | |
| E temp = a[i]; | |
| a[i] = a[j]; | |
| a[j] = temp; | |
| } | |
| } | |
| // Creates an array of the given length, fills it with random | |
| // non-negative integers, and returns it. | |
| public static Integer[] createRandomArray(int length) { | |
| Integer[] a = new Integer[length]; | |
| Random rand = new Random(System.currentTimeMillis()); | |
| for (int i = 0; i < a.length; i++) { | |
| a[i] = rand.nextInt(1000000); | |
| } | |
| return a; | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment