forked from TheAlgorithms/Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathTimSort.java
More file actions
50 lines (42 loc) · 1.53 KB
/
TimSort.java
File metadata and controls
50 lines (42 loc) · 1.53 KB
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
package com.thealgorithms.sorts;
import static com.thealgorithms.sorts.SortUtils.less;
/**
* This is simplified TimSort algorithm implementation. The original one is more complicated.
* <p>
* For more details @see <a href="https://en.wikipedia.org/wiki/Timsort">TimSort Algorithm</a>
*/
class TimSort implements SortAlgorithm {
private static final int SUB_ARRAY_SIZE = 32;
private Comparable[] aux;
@Override
public <T extends Comparable<T>> T[] sort(T[] array) {
final int n = array.length;
InsertionSort insertionSort = new InsertionSort();
for (int i = 0; i < n; i += SUB_ARRAY_SIZE) {
insertionSort.sort(array, i, Math.min(i + SUB_ARRAY_SIZE, n));
}
aux = new Comparable[n];
for (int sz = SUB_ARRAY_SIZE; sz < n; sz = sz + sz) {
for (int lo = 0; lo < n - sz; lo += sz + sz) {
merge(array, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, n - 1));
}
}
return array;
}
private <T extends Comparable<T>> void merge(T[] a, final int lo, final int mid, final int hi) {
int i = lo;
int j = mid + 1;
System.arraycopy(a, lo, aux, lo, hi + 1 - lo);
for (int k = lo; k <= hi; k++) {
if (j > hi) {
a[k] = (T) aux[i++];
} else if (i > mid) {
a[k] = (T) aux[j++];
} else if (less(aux[j], aux[i])) {
a[k] = (T) aux[j++];
} else {
a[k] = (T) aux[i++];
}
}
}
}