forked from thuva4/Algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMergeSortAny.java
More file actions
105 lines (91 loc) · 3.04 KB
/
MergeSortAny.java
File metadata and controls
105 lines (91 loc) · 3.04 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
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
import java.lang.reflect.Array;
import java.util.ArrayList;
/**
* @author Casper Rysgaard
*/
public class MergeSortAny<T extends MaxValue<T> & Comparable<T>>
{
/*
* java class used for sorting any type of list
*/
public static <T extends MaxValue<T> & Comparable<T>> void sort(ArrayList<T> arrayList)
{
mergeSortSplit(arrayList, 0, arrayList.size()-1);
}
private static <T extends MaxValue<T> & Comparable<T>> void mergeSortSplit(ArrayList<T> listToSort, int start, int end)
{
if (start < end)
{
int middle = (start + end) / 2;
mergeSortSplit(listToSort, start, middle);
mergeSortSplit(listToSort, middle+1, end);
merge(listToSort, start, middle, end);
}
}
private static <T extends MaxValue<T> & Comparable<T>> void merge(ArrayList<T> listToSort, int start, int middle, int end)
{
ArrayList<T> A = new ArrayList<T>(listToSort.subList(start, middle+1));
ArrayList<T> B = new ArrayList<T>(listToSort.subList(middle+1, end+1));
A.add(A.get(0).getMaxObject());
B.add(B.get(0).getMaxObject());
int i = 0;
int j = 0;
for (int k = start; k <= end; k++)
{
if (A.get(i).compareTo(B.get(j)) <= 0)
{
listToSort.set(k, A.get(i));
i++;
}
else
{
listToSort.set(k, B.get(j));
j++;
}
}
}
public static <T extends MaxValue<T> & Comparable<T>> void sort(T[] array)
{
mergeSortSplitArray(array, 0, array.length-1);
}
private static <T extends MaxValue<T> & Comparable<T>> void mergeSortSplitArray(T[] listToSort, int start, int end)
{
if (start < end)
{
int middle = (start + end) / 2;
mergeSortSplitArray(listToSort, start, middle);
mergeSortSplitArray(listToSort, middle+1, end);
mergeArray(listToSort, start, middle, end);
}
}
private static <T extends MaxValue<T> & Comparable<T>> void mergeArray(T[] listToSort, int start, int middle, int end)
{
T[] A = (T[]) Array.newInstance(listToSort[0].getClass(),middle-start +2);
T[] B = (T[]) Array.newInstance(listToSort[0].getClass(),end - middle +1);
cloneArray(listToSort, A, start);
cloneArray(listToSort, B, middle+1);
int i = 0;
int j = 0;
for (int k = start; k <= end; k++)
{
if (A[i].compareTo(B[j]) <= 0)
{
listToSort[k] = A[i];
i++;
}
else
{
listToSort[k] = B[j];
j++;
}
}
}
private static <T extends MaxValue<T> & Comparable<T>> void cloneArray(T[] listIn, T[] cloneInto, int start)
{
for (int i = start; i < start+cloneInto.length-1; i++)
{
cloneInto[i - start] = listIn[i];
}
cloneInto[cloneInto.length-1] = listIn[0].getMaxObject();
}
}