Difference between revisions of "MergeSort"

From CSE231 Wiki
Jump to navigation Jump to search
 
(87 intermediate revisions by 4 users not shown)
Line 1: Line 1:
 
=Motivation=
 
=Motivation=
Merge Sort is a elegant example of a divide-and-conquer algorithm which can be straight-forwardly parallelized.  Further, parallelization the combine step in possible which is left as a fun exercise for those so inclined.
+
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=
 
=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 [https://en.wikipedia.org/wiki/Merge_sort this] page. If you took CSE 247, this algorithm should look extremely familiar to you.
+
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 [https://en.wikipedia.org/wiki/Merge_sort the wikipedia page on merge sort].
 +
 
 +
{{CollapsibleYouTube|CS 50 Shorts: Merge Sort|<youtube>Pr2Jf83_kG0</youtube>}}
 +
 
 +
{{CollapsibleYouTube|HackerRank: Merge Sort|<youtube>KF2j-9iSf4Q</youtube>}}
 +
 
 +
{{CollapsibleYouTube|Merge Sort Combine Step|<youtube>YgXWDGZai4s</youtube>}}
 +
 
 
==Visualization==
 
==Visualization==
If you've never seen mergesort before, it may be helpful to take a look at [https://visualgo.net/en/sorting?slide=10 this] page which gives a visual demonstration of the algorithm in practice.
+
If you are unclear on how merge sort works, take a look at the [https://visualgo.net/en/sorting?slide=10 visualgo explanation and visualization of merge sort].
 +
 
 +
[[File:MergeSortViz.png|480px|link=https://visualgo.net/en/sorting?slide=10]]
 +
 
 +
== Work and Span ==
 +
The divide step doesn't do any real significant work- it just calculates the midpoint.  The combine step does all the work of merge sort.  The top-level combine (when its two recursive calls have completed) must do N work.  The next level does two ~N/2 combines.  The level below that performs four ~N/4 combines.  And so on.  The table is <math>N</math> wide and <math>\log N</math> high.  Thus the work of merge sort is <math>O(N\log N)</math>.
 +
 
 +
For N=16:
 +
 
 +
{| class="wikitable" style="text-align:center;"
 +
!
 +
! colspan="16" | <- - - - - - - - - - - - - - N - - - - - - - - - - - - - ->
 +
|-
 +
 +
| colspan="16" | mid
 +
|-
 +
!
 +
| colspan="8" | mid
 +
| colspan="8" | mid
 +
|-
 +
!
 +
| colspan="4" | mid
 +
| colspan="4" | mid
 +
| colspan="4" | mid
 +
| colspan="4" | mid
 +
|-
 +
!
 +
| colspan="2" | mid
 +
| colspan="2" | mid
 +
| colspan="2" | mid
 +
| colspan="2" | mid
 +
| colspan="2" | mid
 +
| colspan="2" | mid
 +
| colspan="2" | mid
 +
| colspan="2" | mid
 +
|-
 +
! ^
 +
| style="background-color:#CCCCFF;" | base
 +
| base
 +
| base
 +
| base
 +
| base
 +
| base
 +
| base
 +
| base
 +
| base
 +
| base
 +
| base
 +
| base
 +
| base
 +
| base
 +
| base
 +
| base
 +
|-
 +
! &#124;
 +
| colspan="2" style="background-color:#CCCCFF;" | combine [0, 2)
 +
| colspan="2" | combine [2, 4)
 +
| colspan="2" | combine [4, 6)
 +
| colspan="2" | combine [6, 8)
 +
| colspan="2" | combine [8, 10)
 +
| colspan="2" | combine [10, 12)
 +
| colspan="2" | combine [12, 14)
 +
| colspan="2" | combine [14, 16)
 +
|-
 +
! lg N
 +
| colspan="4" style="background-color:#CCCCFF;" | combine [0, 4)
 +
| colspan="4" | combine [4, 8)
 +
| colspan="4" | combine [8, 12)
 +
| colspan="4" | combine [12, 16)
 +
|-
 +
! &#124;
 +
| colspan="8" style="background-color:#CCCCFF;" | combine [0, 8)
 +
| colspan="8" | combine [8, 16)
 +
|-
 +
! v
 +
| colspan="16" style="background-color:#CCCCFF;" | combine [0, 16)
 +
|}
 +
 
  
=Utilities=
+
Technically, the span also include log(N) midpoint calculations from the divide steps, this is insignificant next to N, so we focus on just the work/span of the combines.
Both the sequential and parallel merge sorts will be passed a [https://www.cse.wustl.edu/~cosgroved/courses/cse231/current/apidocs/sort/core/merge/Combiner.html Combiner].  When you are done with the divide and conquer phases, invoke [https://www.cse.wustl.edu/~cosgroved/courses/cse231/current/apidocs/sort/core/merge/Combiner.html#combineRange-int:A-int-int-int- combiner.combineRange(data, min, mid, maxExclusive)] to merge the two sorted sub-problem results.
 
  
 +
The grand vast majority of the span for the classic sequential combine merge sort is the work of one combine for each of the levels <span style="background:#CCCCFF">(highlighted in blue)</span>.  This works out to be the [https://en.wikipedia.org/wiki/Geometric_series geometric series]:
  
=Code to Implement=
+
<math>N + \frac{N}{2} + \frac{N}{4} + \frac{N}{8} + \frac{N}{16} + \cdots + 1</math>
{{CodeToImplement|MergeSort|sequentialMergeSort<br>sequentialMergeSortKernel<br>parallelMergeSort<br>parallelMergeSortKernel|sort.studio.merge}}
+
 
 +
which is:
 +
 
 +
<math>2N</math>
 +
 
 +
[[File:Classic_parallel_merge_sort_and_quicksort_span.svg|600px]]
 +
 
 +
As a [[MergeSort_Parallel_Combiner|challenge problem]], we parallelize the combine step, resulting in a span for merge sort of an outstanding <math>\lg^k{}n</math>.
 +
 
 +
=The Core Questions=
 +
*What are the tasks?
 +
*What is the data?
 +
*Is the data mutable?
 +
*If so, how is it shared?
 +
 
 +
=Mistakes To Avoid=
 +
{{warning | Be sure to calculate the midpoint correctly. }}
 +
{{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.}}
 +
{{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 Investigate and 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.
 +
 
 +
==Combine Step==
 +
Both the sequential and parallel merge sorts will be passed a [https://www.cse.wustl.edu/~dennis.cosgrove/courses/cse231/current/apidocs/sort/merge/core/Combiner.html Combiner].  When you are done with the divide and conquer phases, invoke [https://www.cse.wustl.edu/~dennis.cosgrove/courses/cse231/current/apidocs/sort/merge/core/Combiner.html#combine(T%5B%5D,T%5B%5D,java.util.Comparator) combiner.combineRange(a, b, comparator)] to merge the two sorted sub-problem results. For the base case, [https://www.cse.wustl.edu/~dennis.cosgrove/courses/cse231/current/apidocs/sort/merge/core/Combiner.html#createSingleItemArray(T) combiner.createSingleItemArray(item)] is provided.
 +
 
 +
===interface Combiner<T>===
 +
<syntaxhighlight lang="java">
 +
public interface Combiner<T> {
 +
IntFunction<T[]> arrayGenerator();
 +
 
 +
T[] combine(T[] a, T[] b, Comparator<T> comparator) throws InterruptedException, ExecutionException;
 +
 
 +
default T[] createSingleItemArray(T item) {
 +
T[] result = arrayGenerator().apply(1);
 +
result[0] = item;
 +
return result;
 +
}
 +
}
 +
</syntaxhighlight>
 +
 
 +
===class SequentialCombiner<T>===
 +
{{CodeToImplement|SequentialCombiner|constructor<br/>arrayGenerator<br/>combine|sort.merge.exercise}}
 +
 
 +
{{Constructor_1param_4deep|arrayGenerator}}
 +
 
 +
{{Getter_4deep|arrayGenerator}}
 +
====combine====
 +
Implement the combine step.
 +
 
 +
==Sort==
 +
 
 +
===interface Sorter<T>===
 +
 
 +
<syntaxhighlight lang="java">
 +
public interface Sorter<T> {
 +
default void sort(T[] data, Comparator<T> comparator) throws InterruptedException, ExecutionException {
 +
 
 +
throw new NotYetImplementedException();
 +
 
 +
}
 +
 
 +
void sortRange(T[] data, Comparator<T> comparator, int min, int maxExclusive)
 +
throws InterruptedException, ExecutionException;
 +
}
 +
</syntaxhighlight>
 +
 
 +
{{CodeToImplement|Sorter|sort|sort.core}}
 +
 
 +
The [https://www.cse.wustl.edu/~dennis.cosgrove/courses/cse231/spring22/apidocs/sort/core/Sorter.html Sorter<T>] interface provides two methods: [https://www.cse.wustl.edu/~dennis.cosgrove/courses/cse231/spring22/apidocs/sort/core/Sorter.html#sort(T%5B%5D,java.util.Comparator) sort] and [https://www.cse.wustl.edu/~dennis.cosgrove/courses/cse231/spring22/apidocs/sort/core/Sorter.html#sortRange(T%5B%5D,java.util.Comparator,int,int) sortRange].  We will leave sortRange to the classes which implement Sorter.
 +
 
 +
====sort====
 +
 
 +
You will provide a default implementation of the sort method, so that all implementing classes do not have to.
 +
 
 +
{{Sequential|default void sort(T[] data, Comparator<T> comparator)}}
 +
 
 +
You should simply invoke the sortRange method with the correct arguments. Consider whether you should use data.length-1 or data.length as your max, given that we've named the variable <code>maxExclusive</code>.
 +
<!--
 +
==SequentialCombiner==
 +
Merge sort's combine step leverages the fact that it can rely on the two sub-ranges are provided in sorted order.  Use this fact to fill the provided temporary buffer with the sorted contents of the entire range [min, maxExclusive).
 +
 
 +
Performance note: in an effort to make this part of the assignment more appropriately approachable, a temporary buffer will be created, combined into, and copied back from.  Merge sort can be built such that depths of the recursion alternate which buffer is read from and written to.  The added complexity this performance improvement would incur is not deemed valuable from a pedagogical stand point, but it is worth noting.
 +
 
 +
=== (Provided) combineRange ===
 +
The public method <code>combineRange(data, comparator, min, mid, maxExclusive)</code> is provided.  It creates a temporary buffer and passes it to <code>combineRangeIntoBuffer(buffer, data, comparator, min, mid, maxExclusive)</code> which you will implement to fill the temporary buffer with the combined sorted contents.  The contents of the temporary buffer is then copied back to the data array with [https://docs.oracle.com/javase/8/docs/api/java/lang/System.html#arraycopy-java.lang.Object-int-java.lang.Object-int-int- System.arraycopy()].
 +
 
 +
{{CollapsibleCode|combineRange(T[] data, Comparator<T> comparator, int min, int mid, int maxExclusive)|<syntaxhighlight lang="java">@Override
 +
public void combineRange(T[] data, Comparator<T> comparator, int min, int mid, int maxExclusive) {
 +
int rangeLength = maxExclusive - min;
 +
T[] buffer = ArrayUtils.createArray(componentType, rangeLength);
 +
combineRangeIntoBuffer(buffer, data, comparator, min, mid, maxExclusive);
 +
System.arraycopy(buffer, 0, data, min, maxExclusive - min);
 +
}</syntaxhighlight>}}
 +
 
 +
=== (Exercise) combineRangeIntoBuffer ===
 +
{{CodeToImplement|SequentialCombiner|combineRangeIntoBuffer|sort.merge.exercise}}
 +
 
 +
{{Sequential|private static <T> void combineRangeIntoBuffer(T[] buffer, T[] data, Comparator<T> comparator, int min, int mid, int maxExclusive)}}
  
{{Sequential|sequentialMergeSort}}
+
Here you will implement the classic sequential merge combine outlined in the [[#Background|Background]] section.  You will read from <code>data</code> between <code>min</code> and <code>maxExclusive</code> and write to <code>buffer</code> starting at 0.
 +
-->
  
{{Sequential|sequentialMergeSortKernel}}
+
===SequentialMergeSorter===
 +
{{CodeToImplement|SequentialMergeSorter|sortRangeOutOfPlace|sort.merge.exercise}}
  
{{Parallel|parallelMergeSort}}
+
Implement the classic divide and conquer sequential algorithm here. 
  
{{Parallel|parallelMergeSortKernel}}
+
{{Warning| Be sure to leverage the provided <code>private final Combiner<T> combiner;</code> field to perform the combine step.}}
  
=Optional Fun Parallel Combiner=
+
===ParallelMergeSorter===
{{CodeToImplement|ParallelCombiner|parallelCombine|sort.fun.merge}}
+
{{CodeToImplement|ParallelMergeSorter|sortRangeOutOfPlace|sort.merge.exercise}}
  
=Where to Start=
+
Adapt your sequential algorithm to take advantage of what can be parallelized.
  
Navigate to the '''sort.studio.merge''' package and look at the <code>MergeSort.java</code> class. The '''sort.core.merg''' packagecontains some useful building block classes we created for you. Take a look at the <code>MergeableData</code> interface as you will need to use its methods to assist you in this studio.
+
What can be in parallel?
  
=MergeSort Studio=
+
What is dependent on the parallel tasks completing?
  
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 the mergesort method should only call the kernel once. We do this in order to manipulate where we can place our async/finish blocks. When completing this studio, think carefully about where to put your async/finish calls.
+
{{Warning|Leverage the provided <code>private final IntPredicate isParallelDesired;</code> field to test whether or not parallelism is warranted for the current range length.}}
  
 +
{{Warning|Fall back to the provided <code>private final Sorter<T> lowerOverheadSorter;</code> field when the <code>isParallelDesired</code> predicate indicates that parallelism is not longer warranted.}}
 +
<!--
 +
{{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.
  
Hint: Follow the Wikipedia links and look at the pseudocode for help.
+
{{Sequential|public static void sequentialMergeSort(int[] data, Combiner combiner)}}
  
 +
{{Sequential|private static void sequentialMergeSortKernel(int[] data, int lowInclusive, int highExclusive, Combiner combiner)}}
 
==Parallel Implementation==
 
==Parallel Implementation==
 +
This approach should behave much like the sequential implementation, but it should also include async/finish calls. Think carefully about where to place them to maximize concurrency.
  
This should look exactly like the sequential implementation, but it should also include async/finish calls. Think carefully about where to place them to maximize concurrency.
+
Test the length of the range with <code>isParallelPredicate</code> to determine if you should parallelize or fall back to sequential.
 +
 
 +
{{Parallel|public static void parallelMergeSort(int[] data, IntPredicate isParallelPredicate, Combiner combiner)}}
 +
 
 +
{{Parallel|private static void parallelMergeSortKernel(int[] data, int lowInclusive, int highExclusive, IntPredicate isParallelPredicate, Combiner combiner)}}
 +
-->
 +
 
 +
=(Optional) Challenge Parallel Combiner=
 +
You can divide and conquer the combine step in merge sort.  The work should remain <math>\mathcal{O}(n\lg{}n)</math> while the critical path length can be cleanly improved from <math>\mathcal{O}(n)</math> down to <math>\mathcal{O}(\lg^3{}n)</math>.
 +
 
 +
For details on how to complete this challenge, check out: [[MergeSort_Parallel_Combiner]]
  
 
=Testing Your Solution=
 
=Testing Your Solution=
==Correctness==
+
{{TestSuite|__MergeSorterTestSuite|sort.merge.exercise}}
{{TestSuite|MergeSortTestSuite|sort.studio.merge}}
+
 
==Performance==
+
=Client=
{{Performance|SortTiming|sort}}
+
{{Client|MergeSortClient|sort.merge.client|main}}
 +
 
 +
{{CollapsibleCode|MergeSortClient|<syntaxhighlight lang="java">String[] data = createShuffledLetterNumberPairs();
 +
System.out.println("unsorted: " + Arrays.toString(data));
 +
Combiner<String> combiner = new SequentialCombiner<>(String.class);
 +
IntPredicate isParallelDesired = new GreaterThanThreshold(31);
 +
Sorter<String> sorter = new ParallelMergeSorter<>(combiner, isParallelDesired);
 +
sorter.sort(data, Comparator.naturalOrder());
 +
System.out.println("  sorted: " + Arrays.toString(data));</syntaxhighlight>}}
 +
 
 +
=Performance=
 +
{{Performance|SortTiming|sort.merge.performance}}
 +
 
 +
=Pledge, Acknowledgments, Citations=
 +
{{Pledge|studio-merge-sort}}

Latest revision as of 04:09, 8 February 2024

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.

Video: CS 50 Shorts: Merge Sort  
Video: HackerRank: Merge Sort  
Video: Merge Sort Combine Step  

Visualization

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

MergeSortViz.png

Work and Span

The divide step doesn't do any real significant work- it just calculates the midpoint. The combine step does all the work of merge sort. The top-level combine (when its two recursive calls have completed) must do N work. The next level does two ~N/2 combines. The level below that performs four ~N/4 combines. And so on. The table is wide and high. Thus the work of merge sort is .

For N=16:

<- - - - - - - - - - - - - - N - - - - - - - - - - - - - ->
mid
mid mid
mid mid mid mid
mid mid mid mid mid mid mid mid
^ base base base base base base base base base base base base base base base base
| combine [0, 2) combine [2, 4) combine [4, 6) combine [6, 8) combine [8, 10) combine [10, 12) combine [12, 14) combine [14, 16)
lg N combine [0, 4) combine [4, 8) combine [8, 12) combine [12, 16)
| combine [0, 8) combine [8, 16)
v combine [0, 16)


Technically, the span also include log(N) midpoint calculations from the divide steps, this is insignificant next to N, so we focus on just the work/span of the combines.

The grand vast majority of the span for the classic sequential combine merge sort is the work of one combine for each of the levels (highlighted in blue). This works out to be the geometric series:

which is:

Classic parallel merge sort and quicksort span.svg

As a challenge problem, we parallelize the combine step, resulting in a span for merge sort of an outstanding .

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 Investigate and 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.

Combine Step

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(a, b, comparator) to merge the two sorted sub-problem results. For the base case, combiner.createSingleItemArray(item) is provided.

interface Combiner<T>

public interface Combiner<T> {
	IntFunction<T[]> arrayGenerator();

	T[] combine(T[] a, T[] b, Comparator<T> comparator) throws InterruptedException, ExecutionException;

	default T[] createSingleItemArray(T item) {
		T[] result = arrayGenerator().apply(1);
		result[0] = item;
		return result;
	}
}

class SequentialCombiner<T>

class: SequentialCombiner.java Java.png
methods: constructor
arrayGenerator
combine
package: sort.merge.exercise
source folder: student/src/main/java

constructor

Maintain the passed arrayGenerator parameter in a (private final) instance variable for later use.

arrayGenerator

Return the arrayGenerator previously passed to the constructor.

combine

Implement the combine step.

Sort

interface Sorter<T>

public interface Sorter<T> {
	default void sort(T[] data, Comparator<T> comparator) throws InterruptedException, ExecutionException {

		throw new NotYetImplementedException();

	}

	void sortRange(T[] data, Comparator<T> comparator, int min, int maxExclusive)
			throws InterruptedException, ExecutionException;
}
class: Sorter.java Java.png
methods: sort
package: sort.core
source folder: student/src/main/java

The Sorter<T> interface provides two methods: sort and sortRange. We will leave sortRange to the classes which implement Sorter.

sort

You will provide a default implementation of the sort method, so that all implementing classes do not have to.

method: default void sort(T[] data, Comparator<T> comparator) Sequential.svg (sequential implementation only)

You should simply invoke the sortRange method with the correct arguments. Consider whether you should use data.length-1 or data.length as your max, given that we've named the variable maxExclusive.

SequentialMergeSorter

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

Implement the classic divide and conquer sequential algorithm here.

Attention niels epting.svg Warning: Be sure to leverage the provided private final Combiner<T> combiner; field to perform the combine step.

ParallelMergeSorter

class: ParallelMergeSorter.java Java.png
methods: sortRangeOutOfPlace
package: sort.merge.exercise
source folder: student/src/main/java

Adapt your sequential algorithm to take advantage of what can be parallelized.

What can be in parallel?

What is dependent on the parallel tasks completing?

Attention niels epting.svg Warning:Leverage the provided private final IntPredicate isParallelDesired; field to test whether or not parallelism is warranted for the current range length.
Attention niels epting.svg Warning:Fall back to the provided private final Sorter<T> lowerOverheadSorter; field when the isParallelDesired predicate indicates that parallelism is not longer warranted.

(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

class: __MergeSorterTestSuite.java Junit.png
package: sort.merge.exercise
source folder: testing/src/test/java

Client

class: MergeSortClient.java CLIENT
package: sort.merge.client
source folder: student/src/main/java
MergeSortClient  
String[] data = createShuffledLetterNumberPairs();
System.out.println("unsorted: " + Arrays.toString(data));
Combiner<String> combiner = new SequentialCombiner<>(String.class);
IntPredicate isParallelDesired = new GreaterThanThreshold(31);
Sorter<String> sorter = new ParallelMergeSorter<>(combiner, isParallelDesired);
sorter.sort(data, Comparator.naturalOrder());
System.out.println("  sorted: " + Arrays.toString(data));

Performance

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

Pledge, Acknowledgments, Citations

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

More info about the Honor Pledge