EN
Java - merge sort implementation algorithm (custom)
6
points
Merge sort is a D&C (Divide and Conquer) algorithm. Like quick sort average time complexity is O(n log n). But the difference is that merge sort worst time complexity is also O(n log n) as quick sort O(n^2). Qucik sort adventage over merge sort is that it requires less memory, thus quick sort has better space complexity.
Java - merge sort implementation
import java.util.Arrays;
public class SortUtil {
public static void mergeSort(int[] arr) {
int[] buff = new int[arr.length];
mergeSort(arr, buff, 0, arr.length - 1);
}
private static void mergeSort(int[] arr, int[] buff, int lo, int hi) {
if (lo < hi) {
int mid = lo + (hi - lo) / 2;
mergeSort(arr, buff, lo, mid);
mergeSort(arr, buff, mid + 1, hi);
for (int i = lo; i <= hi; i++) {
buff[i] = arr[i];
}
int i = lo;
int j = mid + 1;
int k = lo;
while (i <= mid && j <= hi) {
if (buff[i] <= buff[j]) {
arr[k++] = buff[i++];
} else {
arr[k++] = buff[j++];
}
}
while (i <= mid) {
arr[k++] = buff[i++];
}
}
}
public static void main(String[] args) {
int[] array = {2, 8, 1, 4, 5, 6, 3};
// [2, 8, 1, 4, 5, 6, 3]
System.out.println(Arrays.toString(array));
mergeSort(array);
// [1, 2, 3, 4, 5, 6, 8]
System.out.println(Arrays.toString(array));
}
}
Output:
[2, 8, 1, 4, 5, 6, 3]
[1, 2, 3, 4, 5, 6, 8]
Complex unit test with order assertion
import com.google.common.base.Stopwatch;
import org.junit.Test;
import java.util.Arrays;
import java.util.concurrent.ThreadLocalRandom;
public class SortUtilTests {
@Test
public void test1 () {
int[] array = {2, 8, 1, 4, 5, 6, 3};
System.out.println(Arrays.toString(array));
SortUtil.mergeSort(array);
assertSortedArray(array);
System.out.println(Arrays.toString(array));
}
@Test
public void test2 () {
int[] array = new int[6]; // even number array size
for (int i = 0; i < array.length; i++) {
array[i] = nextInt(100, 2_000_000);
}
System.out.println(Arrays.toString(array));
SortUtil.mergeSort(array);
assertSortedArray(array);
System.out.println(Arrays.toString(array));
}
@Test
public void test3 () {
int[] array = new int[7]; // odd number array size
for (int i = 0; i < array.length; i++) {
array[i] = nextInt(100, 2_000_000);
}
array[4] = 0;
array[1] = Integer.MAX_VALUE;
// [1419647, 155906, 1113132, 702682, 1700450, 1279031, 1326543]
System.out.println(Arrays.toString(array));
SortUtil.mergeSort(array);
assertSortedArray(array);
// [155906, 702682, 1113132, 1279031, 1326543, 1419647, 1700450]
System.out.println(Arrays.toString(array));
}
@Test
public void test4 () {
int[] array = new int[214_578];
for (int i = 0; i < array.length; i++) {
array[i] = nextInt(100, 2_000_000);
}
System.out.println("Array size: " + array.length);
System.out.println("BEFORE sorting - first and last element");
System.out.println(array[0]);
System.out.println(array[array.length - 1]);
Stopwatch stopwatch = Stopwatch.createStarted();
SortUtil.mergeSort(array);
// 48.42 ms
System.out.println(stopwatch.stop());
assertSortedArray(array);
System.out.println("AFTER sorting - first and last element");
System.out.println(array[0]);
System.out.println(array[array.length - 1]);
}
@Test
public void test5 () {
int[] array = new int[5_000_000];
for (int i = 0; i < array.length; i++) {
array[i] = nextInt(100, 2_000_000_000);
}
System.out.println(array[0]);
System.out.println(array[array.length - 1]);
Stopwatch stopwatch = Stopwatch.createStarted();
SortUtil.mergeSort(array);
// 832.2 ms
System.out.println(stopwatch.stop());
assertSortedArray(array);
System.out.println(array[0]);
System.out.println(array[array.length - 1]);
}
private static int nextInt(int min, int max) {
return ThreadLocalRandom.current().nextInt(min, max);
}
private void assertSortedArray(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
if (array[i] > array[i + 1]) {
throw new RuntimeException(
array[i] + " is larger then " + array[i + 1]
+ ", index: " + i + ", index2: " + (i + 1));
}
}
}
}
Compare speed
Now we will compare speed of:
- buble sort
- this article merge sort impelmentation
- quick sort - JDK implementation - Arrays.sort()
Bubble sort only on 50_000 elements array as it takes more then 4 secounds.
Merge sort and quick sort on array of 5_000_000 elements and we use the same seed with Random class to generate the same random numbers to have good comparing test.
import com.google.common.base.Stopwatch;
import org.junit.Test;
import java.util.Arrays;
import java.util.Random;
public class SortUtilCompareTest {
public static int nextInt(int min, int max, Random random) {
return random.nextInt((max - min) + 1) + min;
}
// array of size 50_000 elements
@Test
public void test_simple_bubble_sort () {
Random random = new Random(3819201);
int[] array = new int[50_000];
for (int i = 0; i < array.length; i++) {
int randomInt = nextInt(100, 2_000_000_000, random);
array[i] = randomInt;
}
Stopwatch stopwatch = Stopwatch.createStarted();
// simple bubble sort - O(n ^ 2) time complexity
for (int i = 0; i < array.length; i++) {
for (int j = i + 1; j < array.length; j++) {
if (array[i] > array[j]) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
}
System.out.println(stopwatch.stop()); // 4.236 s
assertSortedArray(array);
}
// array of size 5_000_000 elements
@Test
public void test_our_custom_merge_sort_impl () {
Random random = new Random(3819201);
int[] array = new int[5_000_000];
for (int i = 0; i < array.length; i++) {
int randomInt = nextInt(100, 2_000_000_000, random);
array[i] = randomInt;
}
Stopwatch stopwatch = Stopwatch.createStarted();
SortUtil.mergeSort(array);
System.out.println(stopwatch.stop()); // 889.3 ms
assertSortedArray(array);
}
// array of size 5_000_000 elements
@Test
public void test_jdk_quick_sort () {
Random random = new Random(3819201);
int[] array = new int[5_000_000];
for (int i = 0; i < array.length; i++) {
int randomInt = nextInt(100, 2_000_000_000, random);
array[i] = randomInt;
}
Stopwatch stopwatch = Stopwatch.createStarted();
Arrays.sort(array);
System.out.println(stopwatch.stop()); // 633.3 ms
assertSortedArray(array);
}
private void assertSortedArray(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
if (array[i] > array[i + 1]) {
throw new RuntimeException(
array[i] + " is larger then " + array[i + 1]
+ ", index: " + i + ", index2: " + (i + 1));
}
}
}
}