Difference between revisions of "MergeSort"

From CSE231 Wiki
Jump to navigation Jump to search
Line 35: Line 35:
 
=Code to Implement=
 
=Code to Implement=
 
You will need to implement merge sort sequentially and in parallel, but you will need to do both implementations recursively. The kernel method should call itself using recursion, but each public mergesort method should only call its kernel once to do the work.
 
You will need to implement merge sort sequentially and in parallel, but you will need to do both implementations recursively. The kernel method should call itself using recursion, but each public mergesort method should only call its kernel once to do the work.
 +
 +
==Sorter==
 +
{{CodeToImplement|Sorter|sort|sort.merge.studio}}
 +
 +
Here you will provide the default implementation of the sort method.
 +
 +
<nowiki>default void sort(T[] data, Comparator<T> comparator)</nowiki>
 +
 +
You should simply invoke the sortRange method with the correct arguments.
 +
 +
==SequentialCombiner==
 +
 +
{{CodeToImplement|SequentialCombiner|combineRangeIntoBuffer|sort.merge.studio}}
 +
 +
==SequentialMergeSorter==
 +
 +
{{CodeToImplement|SequentialMergeSorter|sortRange|sort.merge.studio}}
 +
 +
==ParallelMergeSorter==
 +
 +
{{CodeToImplement|ParallelMergeSorter|sortRange|sort.merge.studio}}
 +
 
{{CodeToImplement|MergeSort|sequentialMergeSort<br>sequentialMergeSortKernel<br>parallelMergeSort<br>parallelMergeSortKernel|sort.studio.merge}}
 
{{CodeToImplement|MergeSort|sequentialMergeSort<br>sequentialMergeSortKernel<br>parallelMergeSort<br>parallelMergeSortKernel|sort.studio.merge}}
 +
<!--
 
==Sequential Implementation==
 
==Sequential Implementation==
 
The only thing you will need to edit is the kernel method. As this is a sequential implementation, there is no need to call an async or finish. Using the description of merge sort provided to you in the background, try to consider what the base case would be. Then, further consider how to call the method recursively. When the array reaches the base case, you will need to complete the “merging” aspect of merge sort. As mentioned above, there is a method in the utils class that should help with this.
 
The only thing you will need to edit is the kernel method. As this is a sequential implementation, there is no need to call an async or finish. Using the description of merge sort provided to you in the background, try to consider what the base case would be. Then, further consider how to call the method recursively. When the array reaches the base case, you will need to complete the “merging” aspect of merge sort. As mentioned above, there is a method in the utils class that should help with this.
Line 50: Line 73:
  
 
{{Parallel|private static void parallelMergeSortKernel(int[] data, int lowInclusive, int highExclusive, IntPredicate isParallelPredicate, Combiner combiner)}}
 
{{Parallel|private static void parallelMergeSortKernel(int[] data, int lowInclusive, int highExclusive, IntPredicate isParallelPredicate, Combiner combiner)}}
 +
-->
  
 
=(Optional) Challenge Parallel Combiner=
 
=(Optional) Challenge Parallel Combiner=

Revision as of 17:32, 2 November 2021

Motivation

Sorting is a problem that is well solved by divide and conquer algorithms. Merge sort is a elegant example which can be parallelized in a straight-forward manner.

Finally, parallelization of the combine step, while not trivial, is possible (and left as an optional fun exercise for those so inclined).

Background

In computer science, merge sort refers to a sorting algorithm which splits an array of data into continuously smaller halves until the arrays reach a size of 1, after which the elements are continuously compared and merged into a sorted array.

For more information on how this process works, visit the wikipedia page on merge sort.

Visualization

If you are unclear on how merge sort works, take a look at the visualgo explanation and visualization of merge sort.

MergeSortViz.png

The Core Questions

  • What are the tasks?
  • What is the data?
  • Is the data mutable?
  • If so, how is it shared?

Mistakes To Avoid

Attention niels epting.svg Warning: Be sure to calculate the midpoint correctly.
Attention niels epting.svg Warning: When checking the base case, remember to account for [minInclusive, maxExclusive). It is all too easy to get an off by 1 error and stack overflow.
Attention niels epting.svg Warning: When transitioning to sequential, make sure to NOT sort the entire array when you are only responsible for a range [min,max).

Code to Use

Both the sequential and parallel merge sorts will be passed a Combiner. When you are done with the divide and conquer phases, invoke combiner.combineRange(data, min, mid, maxExclusive) to merge the two sorted sub-problem results.

Code to Implement

You will need to implement merge sort sequentially and in parallel, but you will need to do both implementations recursively. The kernel method should call itself using recursion, but each public mergesort method should only call its kernel once to do the work.

Sorter

class: Sorter.java Java.png
methods: sort
package: sort.merge.studio
source folder: student/src/main/java

Here you will provide the default implementation of the sort method.

default void sort(T[] data, Comparator<T> comparator)

You should simply invoke the sortRange method with the correct arguments.

SequentialCombiner

class: SequentialCombiner.java Java.png
methods: combineRangeIntoBuffer
package: sort.merge.studio
source folder: student/src/main/java

SequentialMergeSorter

class: SequentialMergeSorter.java Java.png
methods: sortRange
package: sort.merge.studio
source folder: student/src/main/java

ParallelMergeSorter

class: ParallelMergeSorter.java Java.png
methods: sortRange
package: sort.merge.studio
source folder: student/src/main/java
class: MergeSort.java Java.png
methods: sequentialMergeSort
sequentialMergeSortKernel
parallelMergeSort
parallelMergeSortKernel
package: sort.studio.merge
source folder: student/src/main/java

(Optional) Challenge Parallel Combiner

You can divide and conquer the combine step in merge sort. The work should remain while the critical path length can be cleanly improved from down to .

For details on how to complete this challenge, check out: MergeSort_Parallel_Combiner

Testing Your Solution

Correctness

class: MergeSortTestSuite.java Junit.png
package: sort.studio.merge
source folder: testing/src/test/java

Performance

class: SortTiming.java Noun Project stopwatch icon 386232 cc.svg
package: sort
source folder: src/main/java

Note: do not be concerned if your implementations run slower than Java's highly optimized Dual Pivot Quicksort.

Pledge, Acknowledgments, Citations

file: studio-merge-sort-pledge-acknowledgments-citations.txt

More info about the Honor Pledge