java merge sorting arrays with objects

Question

I couldn't figure out why my merge sort isn't working.

public static void merge(ArrayList<Coupon> arraylist, int LF, int LL, int RF, int RL) {
        ArrayList<Coupon> tempArr = arraylist;
        int i = LF;
        while (LF <= LL && RF <= RL) {
            if (arraylist.get(LF).getPrice() < arraylist.get(RF).getPrice()) {
                tempArr.Swap(i, LF);
                LF++;   
            } else {
                tempArr.Swap(i, RF);;
                RF++;
            }
            i++;
        }
        while (LF <= LL) {
            tempArr.Swap(i, LF);
            LF++;
            i++;
        }
        while (RF <= RL) {
            tempArr.Swap(i, RF);
            RF++;
            i++;
        }
        arraylist = tempArr;
    }
    
    public static void mergeSort(ArrayList<Coupon> arraylist, int first, int last) {
        if (first < last) {
            int middle = (first + last) / 2;
            mergeSort(arraylist, first, middle);
            mergeSort(arraylist, middle + 1, last);
            merge(arraylist, first, middle, middle+1, last);
        }
    }

I made sure I used it in my main class with correct parameters, I made sure the code actually looped through all the while loops and if-else statements(I checked with system out print in each statement), I also made sure that my Swap method is working by using it elsewhere. Can you help me find what went wrong? Thank you so much in advance!

P.S. LF is left first, LL is left last, RF is right first, RL is right last.

Answer 1

The code is attempting to implement an in-place merge sort, which is more complicated than what the code is currently doing. For example, initial state, i = LF: assume the first compare is arraylist[LF] > arraylist[RF], so a swap of arraylist[i], arraylist[RF] where i == LF is done, then both i and RF are incremented, so what was in arraylist[LF] will end up getting skipped and never compared, when where it is possible that it should be at arraylist[LF+1], but is put at arraylist[RF] and never compared with any other element.

Normally a second array is allocated, and a merge sort merges between the two arrays:

https://en.wikipedia.org/wiki/Merge_sort#Top-down_implementation

Link to an example of an in-place but unstable (doesn't preserve original order of equal elements):

https://stackoverflow.com/a/15657134

Answer 2

Okay. First things first. You should really implement some kind of error checking in the mergeSort() method otherwise the compiler will throw a huge fit if any of the values end up being null or out of bounds. It's much easier to just catch those before they happen.

Secondly, I'm not entirely sure how your code works, since I can't be entirely sure what the getPrice() and swap() methods do. But, here is my implementation of mergeSort() that attempts to transfer some of your functionality over. Hopefully it helps you figure out what's going wrong. (P.S. this mergeSort() implementation was built originally with arrays in mind but it should work for lists too, it just might be more complex than it needs to be for lists)

public static <Coupon> List<Coupon> mergeSort(List<Coupon> l) {
    if (l == null) {
        throw new IllegalArgumentException();
    }
    if (l.size() < 2) { // You don't need to sort a 1 element list
        return l;
    }
    return merge(mergeSort(l.subList(0, (l.size() / 2)), 
            mergeSort(l.subList((l.size() / 2), l.size()));
}
public static <Coupon> List<Coupon> merge(List<Coupon> l1, List<Coupon> l2) {
    List<Coupon> lOut = new ArrayList<>();
    int index1 = 0;
    int index2 = 0;
    int indexOut;
    int totalLength = l1.size() + l2.size();
    for (indexOut = 0; indexOut < totalLength; indexOut++) {
        if (index1 == l1.size()) {
            lOut.set(indexOut, l2.get(index2);
            index2++;
        } else if (index2 == arr2.size()) {
            lOut.set(indexOut, l1.get(index1));
            index1++;
        } else if (l1.get(index1).compareTo(l2.get(index2)) <= 0) {
            lOut.set(indexOut, l1.get(index1));
            index1++;
        } else if (l1.get(index1).compareTo(l2.get(index2)) > 0 {
            lOut.set(indexOut, l2.get(index2));
            index2++;
        } else {
            throw new AssertionError(); // Code should *never* get here (hopefully)
        }
    }
    return lOut;
}