MergeSort.java
import java.util.stream.Collectors;
import java.util.Arrays;
public class MergeSort> {
// Precondition: leftArr and rightArr are sorted.
// Postcondition: outArr is the sorted, merged result of leftArr and rightArr.
private void merge(E[] outArr, E[] leftArr, E[] rightArr) {
// leftArr index
int l = 0;
// rightArr index
int r = 0;
// outArr index
int o = 0;
// Idea: While there are still data in left and right,
// do a comparison between leftArr[l] and rightArr[r]
// putting the lesser element in outArr[o] and incrementing
// indices as appropriate. Once either leftArr or rightArr
// is empty, copy the rest of the contents of the opposite
// array into outArr.
while (l < leftArr.length && r < rightArr.length){
if (leftArr[l].compareTo(rightArr[r]) < 0)
outArr[o++] = leftArr[l++];
else
outArr[o++] = rightArr[r++];
}
while (l < leftArr.length)
outArr[o++] = leftArr[l++];
while (r < rightArr.length)
outArr[o++] = rightArr[r++];
}
public void mergeSort(E[] arr){
// Recursively split the array in half, until size is 1
if (arr.length > 1){
// -- Find the midpoint of arr
int mid = arr.length / 2;
// -- Create a left and right array
E[] leftArr = (E[]) new Comparable[mid];
E[] rightArr = (E[]) new Comparable[arr.length - mid];
// -- Populate them
System.arraycopy(arr, 0, leftArr, 0, mid);
System.arraycopy(arr, mid, rightArr, 0, arr.length - mid);
// -- Recursive call to mergeSort on left, right
mergeSort(leftArr);
mergeSort(rightArr);
// -- Merge left and right, store the result in arr
merge(arr, leftArr, rightArr);
}
}
public void printArr(E[] arr){
System.out.println(Arrays.stream(arr)
.map(Object::toString)
.collect(Collectors.joining(", ")));
}
public static void main(String[] args){
MergeSort ms = new MergeSort<>();
// Testing merge.
Integer left[] = {1,3,5,6,7};
Integer right[] = {1,2,3,4};
Integer out[] = new Integer[9];
ms.merge(out, left, right);
ms.printArr(out);
// Testing mergeSort.
Integer[] arr = {38, 27, 43, 3, 9, 82, 10};
ms.printArr(arr);
ms.mergeSort(arr);
ms.printArr(arr);
}
}
QuickSort.java
import java.util.stream.Collectors;
import java.util.Arrays;
public class QuickSort>{
private void swap(E arr[], int i, int j){
E temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// arr is the full array, we're only looking at the
// segment from first - last.
// We'll return the new position of the pivot element
private int partition(E arr[], int first, int last){
//pivot <- arr[first]
E pivot = arr[first];
//up <- first + 1 (i)
int up = first + 1;
//down <- last (j)
int down = last;
/*
As long as up < down:
1) Compare arr[up] with the pivot element
incrementing up until arr[up] > pivot
2) Compare arr[down] with the pivot element
decrementing down until arr[down] < pivot
3) When up >= down
a) Swap the pivot with arr[down]
b) Return down
4) Swap arr[up] with arr[down]
*/
while ( true ){
while(up < last && arr[up].compareTo(pivot) < 0)
up++;
while(down > first && arr[down].compareTo(pivot) > 0)
down--;
if (up >= down){
swap(arr, first, down);
return down;
}
swap(arr, up, down);
}
}
private void quickSort(E arr[], int first, int last){
if (first < last){
int pivotIndex = partition(arr, first, last);
quickSort(arr, first, pivotIndex-1);
quickSort(arr, pivotIndex+1, last);
}
}
public void quickSort(E arr[]){
quickSort(arr, 0, arr.length-1);
}
public void printArr(E[] arr){
System.out.println(Arrays.stream(arr)
.map(Object::toString)
.collect(Collectors.joining(", ")));
}
public static void main(String[] args){
QuickSort qs = new QuickSort<>();
Integer[] arr = {44, 75, 23, 43, 55, 12, 64, 77, 33};
qs.printArr(arr);
qs.partition(arr, 0, arr.length-1);
qs.printArr(arr);
Integer[] arr2 = {44, 75, 23, 43, 55, 12, 64, 77, 33};
qs.printArr(arr2);
qs.quickSort(arr2);
qs.printArr(arr2);
}
}
MergeSortBench.java
package bench;
import sort.MergeSort;
import java.util.concurrent.TimeUnit;
import java.util.Random;
import java.util.Arrays;
import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Level;
import org.openjdk.jmh.annotations.Measurement;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.OutputTimeUnit;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.Setup;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.annotations.Warmup;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.RunnerException;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;
public class MergeSortBench {
@State(Scope.Thread)
public static class ThreadState{
MergeSort ms;
Integer[] data;
private int count = 1280000;
@Setup(Level.Invocation)
public void prepare(){
ms = new MergeSort<>();
data = new Random().ints().limit(count).boxed().toArray(Integer[]::new);
}
}
@Benchmark
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@Warmup(iterations = 3, time = 3)
@Measurement(iterations = 3, time = 3)
public void mergeAvgTime(ThreadState ts) {
ts.ms.mergeSort(ts.data);
}
public static void main(String[] args) throws RunnerException {
Options opt = new OptionsBuilder()
.include(MergeSortBench.class.getSimpleName())
.forks(1)
.build();
new Runner(opt).run();
}
}
QuickSortBench.java
package bench;
import sort.QuickSort;
import java.util.concurrent.TimeUnit;
import java.util.Random;
import java.util.Arrays;
import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Level;
import org.openjdk.jmh.annotations.Measurement;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.OutputTimeUnit;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.Setup;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.annotations.Warmup;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.RunnerException;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;
public class QuickSortBench {
@State(Scope.Thread)
public static class ThreadState{
QuickSort qs;
Integer[] data;
private int count = 1280000;
@Setup(Level.Invocation)
public void prepare(){
qs = new QuickSort<>();
data = new Random().ints().limit(count).boxed().toArray(Integer[]::new);
}
}
@Benchmark
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@Warmup(iterations = 3, time = 3)
@Measurement(iterations = 3, time = 3)
public void quickAvgTime(ThreadState ts) {
ts.qs.quickSort(ts.data);
}
public static void main(String[] args) throws RunnerException {
Options opt = new OptionsBuilder()
.include(QuickSortBench.class.getSimpleName())
.forks(1)
.build();
new Runner(opt).run();
}
}
Benchmark Results
10000
Benchmark Mode Cnt Score Error Units
InsertionSortBench.insertionAvgTime avgt 15 159.559 ± 2.160 ms/op
MergeSortBench.mergeAvgTime avgt 15 1.523 ± 0.028 ms/op
QuickSortBench.quickAvgTime avgt 15 0.966 ± 0.078 ms/op
SelectionSortBench.selectionAvgTime avgt 15 59.947 ± 0.844 ms/op
20000
Benchmark Mode Cnt Score Error Units
InsertionSortBench.insertionAvgTime avgt 15 979.892 ± 51.781 ms/op
MergeSortBench.mergeAvgTime avgt 15 3.258 ± 0.074 ms/op
QuickSortBench.quickAvgTime avgt 15 2.192 ± 0.105 ms/op
SelectionSortBench.selectionAvgTime avgt 15 256.190 ± 1.797 ms/op
40000
Benchmark Mode Cnt Score Error Units
InsertionSortBench.insertionAvgTime avgt 15 4973.500 ± 189.098 ms/op
MergeSortBench.mergeAvgTime avgt 15 7.075 ± 0.213 ms/op
QuickSortBench.quickAvgTime avgt 15 4.611 ± 0.226 ms/op
SelectionSortBench.selectionAvgTime avgt 15 1236.235 ± 7.409 ms/op
80000
Benchmark Mode Cnt Score Error Units
InsertionSortBench.insertionAvgTime avgt 15 20670.074 ± 350.948 ms/op
MergeSortBench.mergeAvgTime avgt 15 15.053 ± 0.391 ms/op
QuickSortBench.quickAvgTime avgt 15 10.420 ± 0.788 ms/op
SelectionSortBench.selectionAvgTime avgt 15 5556.927 ± 258.561 ms/op
160000
Benchmark Mode Cnt Score Error Units
MergeSortBench.mergeAvgTime avgt 15 34.740 ± 2.166 ms/op
QuickSortBench.quickAvgTime avgt 15 22.368 ± 1.040 ms/op
320000
Benchmark Mode Cnt Score Error Units
MergeSortBench.mergeAvgTime avgt 15 72.416 ± 2.600 ms/op
QuickSortBench.quickAvgTime avgt 15 51.450 ± 1.560 ms/op
640000
Benchmark Mode Cnt Score Error Units
MergeSortBench.mergeAvgTime avgt 15 174.527 ± 10.733 ms/op
QuickSortBench.quickAvgTime avgt 15 125.274 ± 6.982 ms/op
1280000
Benchmark Mode Cnt Score Error Units
MergeSortBench.mergeAvgTime avgt 15 398.901 ± 17.533 ms/op
QuickSortBench.quickAvgTime avgt 15 294.869 ± 15.711 ms/op