Merge sort in Java
Sort an array by divide and conquer. Sort each half, then merge the two sorted halves into one sorted array.
- File
MergeSort.java, 38 lines- Level
- Toolchain
- JDK 25, JUnit 5
- Test framework
- JUnit 5
- Run the tests
javac and the JUnit console launcher
// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/merge-sort/. The authors are listed in prov/4MRG7S.jsonl.
/** Merge sort. */
public final class MergeSort {
private MergeSort() {}
/** Sorts a in place, in non-decreasing order. */
public static void sort(long[] a) {
long[] b = new long[(a.length + 1) / 2];
sort(a, 0, a.length, b);
}
private static void sort(long[] a, int lo, int hi, long[] b) {
if (hi - lo <= 1) return; // @line L1
int mid = lo + (hi - lo) / 2; // @line L2
sort(a, lo, mid, b); // @line L3
sort(a, mid, hi, b); // @line L4
merge(a, lo, mid, hi, b); // @line L5
}
private static void merge(long[] a, int lo, int mid, int hi, long[] b) {
int m = mid - lo;
System.arraycopy(a, lo, b, 0, m); // @line L6
int i = 0, j = mid, k = lo; // @line L7
while (i < m && j < hi) { // @line L8
if (b[i] <= a[j]) { // @line L9
a[k] = b[i++];
} else {
a[k] = a[j++]; // @line L10
}
k++; // @line L11
}
while (i < m) { // @line L12
a[k++] = b[i++]; // @line L13
}
}
}
MergeSortTest.java 40 lines
// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/merge-sort/. The authors are listed in prov/4MRG7S.jsonl.
import static org.junit.jupiter.api.Assertions.assertArrayEquals;
import java.util.Arrays;
import java.util.Random;
import org.junit.jupiter.api.Test;
class MergeSortTest {
@Test
void example() {
long[] a = {38, 27, 43, 3, 9, 82, 10};
MergeSort.sort(a);
assertArrayEquals(new long[] {3, 9, 10, 27, 38, 43, 82}, a);
}
@Test
void edges() {
for (long[] a : new long[][] {{}, {1}, {2, 1}, {1, 1, 1}, {3, 2, 1}}) {
long[] want = a.clone();
Arrays.sort(want);
MergeSort.sort(a);
assertArrayEquals(want, a);
}
}
@Test
void randomAgainstArraysSort() {
Random rng = new Random(2150);
for (int t = 0; t < 500; t++) {
long[] a = new long[rng.nextInt(61)];
for (int i = 0; i < a.length; i++) a[i] = rng.nextInt(101) - 50;
long[] want = a.clone();
Arrays.sort(want);
MergeSort.sort(a);
assertArrayEquals(want, a);
}
}
}
What the next level needs
- the native tests did not run in this build
- I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work