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.
xxxxxxxxxx1
import java.util.Arrays;2
3
public class SortUtil {4
5
public static void mergeSort(int[] arr) {6
int[] buff = new int[arr.length];7
mergeSort(arr, buff, 0, arr.length - 1);8
}9
10
private static void mergeSort(int[] arr, int[] buff, int lo, int hi) {11
if (lo < hi) {12
int mid = lo + (hi - lo) / 2;13
mergeSort(arr, buff, lo, mid);14
mergeSort(arr, buff, mid + 1, hi);15
16
for (int i = lo; i <= hi; i++) {17
buff[i] = arr[i];18
}19
int i = lo;20
int j = mid + 1;21
int k = lo;22
23
while (i <= mid && j <= hi) {24
if (buff[i] <= buff[j]) {25
arr[k++] = buff[i++];26
} else {27
arr[k++] = buff[j++];28
}29
}30
while (i <= mid) {31
arr[k++] = buff[i++];32
}33
}34
}35
36
public static void main(String[] args) {37
int[] array = {2, 8, 1, 4, 5, 6, 3};38
39
// [2, 8, 1, 4, 5, 6, 3]40
System.out.println(Arrays.toString(array));41
42
mergeSort(array);43
44
// [1, 2, 3, 4, 5, 6, 8]45
System.out.println(Arrays.toString(array));46
}47
}Output:
xxxxxxxxxx1
[2, 8, 1, 4, 5, 6, 3]2
[1, 2, 3, 4, 5, 6, 8]xxxxxxxxxx1
import com.google.common.base.Stopwatch;2
import org.junit.Test;3
4
import java.util.Arrays;5
import java.util.concurrent.ThreadLocalRandom;6
7
public class SortUtilTests {8
9
10
public void test1 () {11
int[] array = {2, 8, 1, 4, 5, 6, 3};12
System.out.println(Arrays.toString(array));13
14
SortUtil.mergeSort(array);15
assertSortedArray(array);16
System.out.println(Arrays.toString(array));17
}18
19
20
public void test2 () {21
int[] array = new int[6]; // even number array size22
for (int i = 0; i < array.length; i++) {23
array[i] = nextInt(100, 2_000_000);24
}25
System.out.println(Arrays.toString(array));26
27
SortUtil.mergeSort(array);28
assertSortedArray(array);29
System.out.println(Arrays.toString(array));30
}31
32
33
public void test3 () {34
int[] array = new int[7]; // odd number array size35
for (int i = 0; i < array.length; i++) {36
array[i] = nextInt(100, 2_000_000);37
}38
39
array[4] = 0;40
array[1] = Integer.MAX_VALUE;41
42
// [1419647, 155906, 1113132, 702682, 1700450, 1279031, 1326543]43
System.out.println(Arrays.toString(array));44
45
SortUtil.mergeSort(array);46
assertSortedArray(array);47
48
// [155906, 702682, 1113132, 1279031, 1326543, 1419647, 1700450]49
System.out.println(Arrays.toString(array));50
}51
52
53
public void test4 () {54
int[] array = new int[214_578];55
for (int i = 0; i < array.length; i++) {56
array[i] = nextInt(100, 2_000_000);57
}58
59
System.out.println("Array size: " + array.length);60
61
System.out.println("BEFORE sorting - first and last element");62
System.out.println(array[0]);63
System.out.println(array[array.length - 1]);64
65
Stopwatch stopwatch = Stopwatch.createStarted();66
SortUtil.mergeSort(array);67
68
// 48.42 ms69
System.out.println(stopwatch.stop());70
71
assertSortedArray(array);72
73
System.out.println("AFTER sorting - first and last element");74
System.out.println(array[0]);75
System.out.println(array[array.length - 1]);76
}77
78
79
public void test5 () {80
int[] array = new int[5_000_000];81
for (int i = 0; i < array.length; i++) {82
array[i] = nextInt(100, 2_000_000_000);83
}84
85
System.out.println(array[0]);86
System.out.println(array[array.length - 1]);87
88
Stopwatch stopwatch = Stopwatch.createStarted();89
SortUtil.mergeSort(array);90
91
// 832.2 ms92
System.out.println(stopwatch.stop());93
94
assertSortedArray(array);95
96
System.out.println(array[0]);97
System.out.println(array[array.length - 1]);98
}99
100
private static int nextInt(int min, int max) {101
return ThreadLocalRandom.current().nextInt(min, max);102
}103
104
private void assertSortedArray(int[] array) {105
for (int i = 0; i < array.length - 1; i++) {106
if (array[i] > array[i + 1]) {107
throw new RuntimeException(108
array[i] + " is larger then " + array[i + 1]109
+ ", index: " + i + ", index2: " + (i + 1));110
}111
}112
}113
}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.
xxxxxxxxxx1
import com.google.common.base.Stopwatch;2
import org.junit.Test;3
4
import java.util.Arrays;5
import java.util.Random;6
7
public class SortUtilCompareTest {8
9
public static int nextInt(int min, int max, Random random) {10
return random.nextInt((max - min) + 1) + min;11
}12
13
// array of size 50_000 elements14
15
public void test_simple_bubble_sort () {16
Random random = new Random(3819201);17
18
int[] array = new int[50_000];19
20
for (int i = 0; i < array.length; i++) {21
int randomInt = nextInt(100, 2_000_000_000, random);22
array[i] = randomInt;23
}24
25
Stopwatch stopwatch = Stopwatch.createStarted();26
27
// simple bubble sort - O(n ^ 2) time complexity28
for (int i = 0; i < array.length; i++) {29
for (int j = i + 1; j < array.length; j++) {30
if (array[i] > array[j]) {31
int tmp = array[i];32
array[i] = array[j];33
array[j] = tmp;34
}35
}36
}37
38
System.out.println(stopwatch.stop()); // 4.236 s39
40
assertSortedArray(array);41
}42
43
// array of size 5_000_000 elements44
45
public void test_our_custom_merge_sort_impl () {46
Random random = new Random(3819201);47
48
int[] array = new int[5_000_000];49
50
for (int i = 0; i < array.length; i++) {51
int randomInt = nextInt(100, 2_000_000_000, random);52
array[i] = randomInt;53
}54
55
Stopwatch stopwatch = Stopwatch.createStarted();56
SortUtil.mergeSort(array);57
System.out.println(stopwatch.stop()); // 889.3 ms58
59
assertSortedArray(array);60
}61
62
// array of size 5_000_000 elements63
64
public void test_jdk_quick_sort () {65
Random random = new Random(3819201);66
67
int[] array = new int[5_000_000];68
69
for (int i = 0; i < array.length; i++) {70
int randomInt = nextInt(100, 2_000_000_000, random);71
array[i] = randomInt;72
}73
74
Stopwatch stopwatch = Stopwatch.createStarted();75
Arrays.sort(array);76
System.out.println(stopwatch.stop()); // 633.3 ms77
78
assertSortedArray(array);79
}80
81
private void assertSortedArray(int[] array) {82
for (int i = 0; i < array.length - 1; i++) {83
if (array[i] > array[i + 1]) {84
throw new RuntimeException(85
array[i] + " is larger then " + array[i + 1]86
+ ", index: " + i + ", index2: " + (i + 1));87
}88
}89
}90
}