How can I fix the merge sort algorithm in Java and return sorted array from function

Question

I have a problem with implementing a merge sort algorithm in Java: I've done merge sort algorithm but it couldn't produce the right result. I also return the sorted list from the function. How can I also do it?

Here is my merge sort algorithm defined below.

mergeSort method:

public static void mergeSort(ArrayList<Person> personList, Comparator<Person> compTr) {
    ArrayList<Person> helper = new ArrayList<Person>();
    mergeSort(personList, helper, 0, personList.size() - 1, compTr);
}

mergeSort function:

private static void mergeSort(ArrayList<Person> list, 
                              ArrayList<Person> helper, 
                              int low, 
                              int high, 
                              Comparator<Person> compTr) {
    if (low < high) {
        int middle = (low + high) / 2;
        mergeSort(list, helper, low, middle, compTr); //sort left half
        mergeSort(list, helper, middle + 1, high, compTr); //sort right half
        merge(list, helper, low, middle, high, compTr); // merge
    }
}

merge algorithm:

private static void merge(ArrayList<Person> list, 
                          ArrayList<Person> helper, 
                          int low, 
                          int middle, 
                          int high,
                          Comparator<Person> compTr) {
    //This loop throws Exception
    for (int i = low; i < high + 1; i++) {
        helper.add(i, list.get(i));
    }

    int helperLeft = low;
    int helperRight = middle + 1;
    int current = low;

    while (helperLeft < middle && helperRight < high) {
        if (isGreaterThan(helper.get(helperLeft), helper.get(helperRight), compTr)) {
            list.set(current, helper.get(helperLeft));
            helperLeft++;
        } else {
            list.set(current, helper.get(helperRight));
            helperRight++;
        }
        current++;
    }

    //Copy remaining elements
    int remaining = middle - helperLeft;
    for (int j = 0; j <= remaining; j++) {
        list.set(current + j, helper.get(helperLeft + j));
    }

    // RETURN LIST(list) _-> TO DO 
}

Implement Comparator feature

public static boolean isGreaterThan(Person helperLeft, Person helperRight, Comparator<Person> compTr) {
    return greaterThan(compTr, helperLeft, helperRight);
}

private static boolean greaterThan(Comparator comp, Person x, Person y) {
    return comp.compare(x, y) > 0;
}

How can I do this?

Answer 1

There is no need to return the sorted array: the array is sorted in place.

Note however these problems:

• the helper array should be allocated with an initial size equal to the size of the array to be sorted. This avoids the problem with helper.add(i, list.get(i)); that keeps inserting extra elements in the middle of the helper array. This is very inefficient: it requires O(n*log(n)) extra space instead of just O(n) and has a time complexity of O(nnlog(n)) which is worse than that of insertion sort.

  You would allocate the helper array with

    ArrayList<Person> helper = new ArrayList<Person>(personList);
  

  and you would save the array elements with helper.set(i, list.get(i)).

• the for loop in merge should iterate up to and including the upper bounds:

    while (helperLeft <= middle && helperRight <= high) 
  

The convention of including the upper bound is confusing and error prone, it is much simpler to exclude the upper bounds as it removes the need for -1 / +1 adjustments.

Here is a modified version:

public static void mergeSort(ArrayList<Person> personList, Comparator<Person> compTr) {
    ArrayList<Person> helper = new ArrayList<Person>(personList);
    mergeSort(personList, helper, 0, personList.size(), compTr);
}

private static void mergeSort(ArrayList<Person> list, 
                              ArrayList<Person> helper, 
                              int low, 
                              int high, 
                              Comparator<Person> compTr) {
    if (high - low >= 2) {
        int middle = low + (high - low) / 2;
        mergeSort(list, helper, low, middle, compTr); //sort left half
        mergeSort(list, helper, middle, high, compTr); //sort right half
        merge(list, helper, low, middle, high, compTr); // merge
    }
}

private static void merge(ArrayList<Person> list, 
                          ArrayList<Person> helper, 
                          int low, 
                          int middle, 
                          int high,
                          Comparator<Person> compTr) {

    for (int i = low; i < high; i++) {
        helper.set(i, list.get(i));
    }

    int helperLeft = low;
    int helperRight = middle;
    int current = low;

    while (helperLeft < middle && helperRight < high) {
        if (isGreaterThan(helper.get(helperLeft), helper.get(helperRight), compTr)) {
            list.set(current, helper.get(helperLeft));
            helperLeft++;
        } else {
            list.set(current, helper.get(helperRight));
            helperRight++;
        }
        current++;
    }

    // Copy remaining elements
    while (helperLeft < middle) {
        list.set(current, helper.get(helperLeft));
        helperLeft++;
        current++;
    }
}

Answer 2

Here is my answer

I changed the code

 while(helperLeft < middle && helperRight < high) {

to

 while(helperLeft <= middle && helperRight <= high) {

Answer 3

I couldn't get a return value as a list from merge function

If I understand you correctly, you are looking for a way to return your sorted list. But in your implementation, you are trying to sort the original list.
That means that you already have a variable pointing to the resulting, sorted list when you call the merge funtion: the variable you use as parameter when calling

public static void mergeSort(ArrayList<Person> personList, Comparator<Person> compTr)

For example, if you have your persons in an ArrayList called "list", you are sorting this "list".

    ArrayList<Person> list = new ArrayList<>();
    for (int i = 0; i < 10; i++) {
        list.add(new Person());
    }
    System.out.println(list);
    mergeSort(list, Comparator.<Person>naturalOrder());
    System.out.println(list);

For more information, what you are using is called a inout parameter - as in you give the function your input and receive its output over this parameter.

---

As pointed out in the comments there also are other problems with the code. I suspect one error is here (<= instead of <)

(helperRight <= high)

and another to be that you used a temp list in an inplace merge sort.

Here a working example can be found: How to sort in-place using the merge sort algorithm?