I've been trying to understand how to do a proper merge sort without utilizing more than one temporary array, simply only using one. However, when I test it, it improperly sorts, and also goes out of the array bounds. I've tried to figure out how to do it multiple times with various different coding sources and ideas, but I haven't had any luck whatsoever. Here is my code:
import java.util.ArrayList;
public class ArrayListSorter{
public static <T extends Comparable<? super T>> void mergesort(ArrayList<T> list) {
ArrayList<T> tempList = generateArrayList(list.size());
mergesort(list, tempList, 0, list.size()-1);
}
//helper method for merge sort driver
public static <T extends Comparable<? super T>> void mergesort(ArrayList<T> list, ArrayList<T> tempList, int start, int end) {
if(list.get(start + 1).compareTo(list.get(end)) < 0) {
int mid = (start + end)/2;
mergesort(list, tempList, start, mid);
mergesort(list, tempList, mid, end);
merge(list, tempList, start, mid, end);
}
}
//For merging two sub arrays together
private static <T extends Comparable<? super T>> void merge(ArrayList<T> list, ArrayList<T> tempList, int left, int mid, int right) {
int i = left;
int j = mid;
int k = left;
while(i <= mid && j <= right)
{
if (list.get(i).compareTo(list.get(j)) <= 0)
{
tempList.set(k, list.get(i));
i++;
} else {
tempList.set(k, list.get(j));
j++;
}
k++;
}
while (i <= mid) {
tempList.set(k, list.get(i));
i++;
k++;
}
while (j <= right)
{
tempList.set(k, list.get(j));
j++;
k++;
}
int l = 0;
while(l < list.size())
{
list.set(l, tempList.get(i));
l++;
}
}
private static <T> ArrayList<T> generateArrayList(int n){
ArrayList<T> list = new ArrayList<T>();
for(int i = 0; i < n; i++) {
list.add(null);
}
return list;
}
}
I would like to use a single arrayList and simply maintain the pointer positions in order to treat it as if there were two arrays.
in method
public static <T extends Comparable<? super T>> void mergesort(ArrayList<T> list, ArrayList<T> tempList, int start, int end) {
this line may has problems
list.get(start + 1).compareTo(list.get(end)) < 0
in classic implementation, this line should compare index rather than list element
// my implementation
private static void recursiveMergeSort(double[] array, int start, int end) {
if ((end - start) > 1) {
int middle = (start + end) / 2;
recursiveMergeSort(array, start, middle);
recursiveMergeSort(array, middle, end);
int left_len = middle - start;
int right_len = end - middle;
var left_cache = new double[left_len];
var right_cache = new double[right_len];
merge(array, start, left_cache, right_cache);
}
}
Another problem you have is index inclusion, you have
mergesort(list, tempList, 0, list.size()-1);
index is left and right included, then see your code
mergesort(list, tempList, start, mid);
mergesort(list, tempList, mid, end);
merge(list, tempList, start, mid, end);
You have overlap in the "mid". My suggestion is to follow conventional index inclusion, that is left included and right excluded.
The last problem is in the code block below. Full copy will erase your original list and you should only copy a fraction of list each "merge" call
int l = 0;
while(l < list.size())
{
list.set(l, tempList.get(i));
l++;
}
You idea is right to avoid too many arrays inistialization, and I don't find any problems in its implementation
BTW, I have a suggestion that you should use breakpoint to debug your program. It is easy to check status of variables in the middle of running program without print.