-
Notifications
You must be signed in to change notification settings - Fork 0
/
MergeSort.java
123 lines (94 loc) · 4.2 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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
/**
* Am implementation of MergeSort
*
* @author Rhys Walker
* @version 1.1
* @since 2023-12-11
*/
import java.util.ArrayList;
public class MergeSort{
// |------------------------------------------------------|
// | FOR INTEGERS |
// |------------------------------------------------------|
/**
* A function that sorts an ArrayList containing integers
* @param listToSort The list that is going to be sorted
* @return A sorted list
*/
public ArrayList<Integer> mergeSort(ArrayList<Integer> listToSort){
// get the length of the list
int length = listToSort.size();
// if reached size 1 then we are at minimum size and must start merging.
if (length == 1){
return listToSort;
}
// calculate half so we can work out what index to swap on
int half = (length+1)/2; // adding and div by two to make it round up
// create arrays to add to for each side
ArrayList<Integer> feedingLeft = new ArrayList<Integer>();
ArrayList<Integer> feedingRight = new ArrayList<Integer>();
// loop over the main array and add to the side that is needed
for (int index = 0; index < listToSort.size(); index++){
if (index <= half-1){ // add to list to be sent left
feedingLeft.add(listToSort.get(index));
}
else if(index > half-1){ // add to list to be sent right
feedingRight.add(listToSort.get(index));
}
}
// recursively call the mergeSort function to split list
ArrayList<Integer> leftHalf = mergeSort(feedingLeft);
ArrayList<Integer> rightHalf = mergeSort(feedingRight);
// merge the lists together
ArrayList<Integer> sortedList = merge(leftHalf, rightHalf);
return sortedList;
}
/**
* A function to merge the ArrayLists containing integers
* @param listToMerge The individual lists that we are going to merge
* @return The merged lists
*/
private ArrayList<Integer> merge(ArrayList<Integer> leftHalf, ArrayList<Integer> rightHalf){
// define the sorted list
ArrayList<Integer> sortedList = new ArrayList<Integer>();
// define the indexs for both sides of the merge
int leftIndex = 0;
int rightIndex = 0;
// failing because once we add the last item from the list we have an index above what we should have
// loop over for the length of both lists to calculate
while (leftIndex<leftHalf.size() || rightIndex<rightHalf.size()){
// if the index is out of range then we must just add the rest of the list thats left
if(leftIndex >= leftHalf.size() || rightIndex >= rightHalf.size()){
if(leftIndex >= leftHalf.size()){ // if left index is out of range we need to add the rest of right
while (rightIndex<rightHalf.size()){ // add whats left
sortedList.add(rightHalf.get(rightIndex));
rightIndex++;
}
}
else{ // if not left then right
while (leftIndex<leftHalf.size()){ // add whats left
sortedList.add(leftHalf.get(leftIndex));
leftIndex++;
}
}
}
else{ // executes as long as one index is no longer out of range
if (leftHalf.get(leftIndex) < rightHalf.get(rightIndex)){
// add to the sorted list
sortedList.add(leftHalf.get(leftIndex));
// incremement counters
leftIndex++;
}
// if left is not smaller then right is
else{
// add to the sorted list
sortedList.add(rightHalf.get(rightIndex));
// increment counters
rightIndex++;
}
}
}
// return it sorted
return sortedList;
}
}