I've become a bit rusty in Java. This is an attempt at brushing up my skills.
In computer science, merge sort is an efficient, general-purpose, comparison-based sorting algorithm.
Questions
- How can I improve my test cases? (TestNG)
- I've used Java-11 here, can I use better idioms?
- Can this implementation improved for performance?
- Can style / readability improved?
Code
Sorting.java
import java.util.Arrays;
import java.util.Comparator;
import java.util.Objects;
public class Sorting {
/**
* Day 08 - Merge Sort
*
* @param data data array
* @param comparator comparator of given data type
* @param ascending sort order
* @param <T> data type
* @return sorted array (in place)
*/
public static <T> T[] mergeSort(T[] data, Comparator<T> comparator, boolean ascending) {
Objects.requireNonNull(data);
Objects.requireNonNull(comparator);
if (data.length <= 1) return data;
var actualComparator = ascending ? comparator : comparator.reversed();
return mergeSort(data, actualComparator, 0, data.length - 1);
}
private static <T> T[] mergeSort(T[] data, Comparator<T> comparator, int start, int stop) {
if (start >= stop) return data;
int pivot = start + (stop - start) / 2;
mergeSort(data, comparator, start, pivot);
mergeSort(data, comparator, pivot + 1, stop);
return merge(data, comparator, start, pivot, stop);
}
private static <T> T[] merge(T[] data, Comparator<T> comparator, int start, int pivot, int stop) {
T[] left = Arrays.copyOfRange(data, start, pivot + 1);
T[] right = Arrays.copyOfRange(data, pivot + 1, stop + 1);
int lPos = 0;
int rPos = 0;
int pos = start;
while (lPos < left.length && rPos < right.length) {
if (comparator.compare(left[lPos], right[rPos]) <= 0) {
data[pos++] = left[lPos++];
} else {
data[pos++] = right[rPos++];
}
}
while (lPos < left.length) {
data[pos++] = left[lPos++];
}
while (rPos < right.length) {
data[pos++] = right[rPos++];
}
return data;
}
}
TestMergeSorting.java
import org.testng.Assert;
import org.testng.annotations.Test;
public class TestMergeSorting {
@Test
public void testMergeSort() {
Assert.assertEquals(asc(6, 5, 9, 3, 2, 1), ar(1, 2, 3, 5, 6, 9));
Assert.assertEquals(asc(1, 1, 1, 1, 2, 1), ar(1, 1, 1, 1, 1, 2));
Assert.assertEquals(asc(2, 1, 1, 1, 1, 2, 1), ar(1, 1, 1, 1, 1, 2, 2));
Assert.assertEquals(asc(1, 1, 1, 1, 1, 2, 1), ar(1, 1, 1, 1, 1, 1, 2));
Assert.assertEquals(asc(3, 2, 1), ar(1, 2, 3));
Assert.assertEquals(asc(1, 2, 3), ar(1, 2, 3));
Assert.assertEquals(asc(2, 0, -1, 2, 1), ar(-1, 0, 1, 2, 2));
Assert.assertEquals(dsc(1, 2, 3), ar(3, 2, 1));
Assert.assertEquals(dsc(3, 2, 1), ar(3, 2, 1));
Assert.assertEquals(dsc(2, 0, -1, 2, 1), ar(2, 2, 1, 0, -1));
Assert.assertEquals(asc(2, 1), ar(1, 2));
Assert.assertEquals(asc(1), ar(1));
Assert.assertEquals(asc(), ar());
Assert.assertEquals(dsc(1), ar(1));
Assert.assertEquals(dsc(), ar());
}
@Test(expectedExceptions = {NullPointerException.class})
public void testNullExcept() {
Sorting.mergeSort(null, Integer::compare, true);
}
private static Integer[] ar(Integer... objects) {
return objects;
}
private static Integer[] asc(Integer... objects) {
return Sorting.mergeSort(objects, Integer::compare, true);
}
private static Integer[] dsc(Integer... objects) {
return Sorting.mergeSort(objects, Integer::compare, false);
}
}