Skip to content

Instantly share code, notes, and snippets.

@CarrCodes

CarrCodes/ParallelMergeSorter.Java

Created December 8, 2017 23:27
Show Gist options
  • Save CarrCodes/1174f1ab0f75bb4789d043e907b7710b to your computer and use it in GitHub Desktop.
Save CarrCodes/1174f1ab0f75bb4789d043e907b7710b to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. Taylor Carr created this gist Dec 8, 2017.
    148 changes: 148 additions & 0 deletions ParallelMergeSorter.Java
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,148 @@
    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];
    }
    }
    }
    104 changes: 104 additions & 0 deletions ParallelSortTester.java
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,104 @@
    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;
    }
    }