-
Notifications
You must be signed in to change notification settings - Fork 1.8k
/
MergeSort.java
108 lines (101 loc) · 3.56 KB
/
MergeSort.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
package com.jwetherell.algorithms.sorts;
/**
* Merge sort is an O(n log n) comparison-based sorting algorithm. Most
* implementations produce a stable sort, which means that the implementation
* preserves the input order of equal elements in the sorted output.
* <p>
* Family: Merging.<br>
* Space: In-place.<br>
* Stable: True.<br>
* <p>
* Average case = O(n*log n)<br>
* Worst case = O(n*log n)<br>
* Best case = O(n*log n)<br>
* <p>
* @see <a href="https://en.wikipedia.org/wiki/Merge_sort">Merge Sort (Wikipedia)</a>
* <br>
* @author Justin Wetherell <phishman3579@gmail.com>
*/
@SuppressWarnings("unchecked")
public class MergeSort<T extends Comparable<T>> {
public static enum SPACE_TYPE { IN_PLACE, NOT_IN_PLACE }
private MergeSort() { }
public static <T extends Comparable<T>> T[] sort(SPACE_TYPE type, T[] unsorted) {
sort(type, 0, unsorted.length, unsorted);
return unsorted;
}
private static <T extends Comparable<T>> void sort(SPACE_TYPE type, int start, int length, T[] unsorted) {
if (length > 2) {
int aLength = (int) Math.floor(length / 2);
int bLength = length - aLength;
sort(type, start, aLength, unsorted);
sort(type, start + aLength, bLength, unsorted);
if (type == SPACE_TYPE.IN_PLACE)
mergeInPlace(start, aLength, start + aLength, bLength, unsorted);
else
mergeWithExtraStorage(start, aLength, start + aLength, bLength, unsorted);
} else if (length == 2) {
T e = unsorted[start + 1];
if (e.compareTo(unsorted[start]) < 0) {
unsorted[start + 1] = unsorted[start];
unsorted[start] = e;
}
}
}
private static <T extends Comparable<T>> void mergeInPlace(int aStart, int aLength, int bStart, int bLength, T[] unsorted) {
int i = aStart;
int j = bStart;
int aSize = aStart + aLength;
int bSize = bStart + bLength;
while (i < aSize && j < bSize) {
T a = unsorted[i];
T b = unsorted[j];
if (b.compareTo(a) < 0) {
// Shift everything to the right one spot
System.arraycopy(unsorted, i, unsorted, i+1, j-i);
unsorted[i] = b;
i++;
j++;
aSize++;
} else {
i++;
}
}
}
private static <T extends Comparable<T>> void mergeWithExtraStorage(int aStart, int aLength, int bStart, int bLength, T[] unsorted) {
int count = 0;
T[] output = (T[]) new Comparable[aLength + bLength];
int i = aStart;
int j = bStart;
int aSize = aStart + aLength;
int bSize = bStart + bLength;
while (i < aSize || j < bSize) {
T a = null;
if (i < aSize) {
a = unsorted[i];
}
T b = null;
if (j < bSize) {
b = unsorted[j];
}
if (a != null && b == null) {
output[count++] = a;
i++;
} else if (b != null && a == null) {
output[count++] = b;
j++;
} else if (b != null && b.compareTo(a) <= 0) {
output[count++] = b;
j++;
} else {
output[count++] = a;
i++;
}
}
int x = 0;
int size = aStart + aLength + bLength;
for (int y = aStart; y < size; y++) {
unsorted[y] = output[x++];
}
}
}