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 personList, Comparator compTr) {
    ArrayList helper = new ArrayList();
    mergeSort(personList, helper, 0, personList.size() - 1, compTr);
}

mergeSort function:

private static void mergeSort(ArrayList list, 
                              ArrayList helper, 
                              int low, 
                              int high, 
                              Comparator 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 list, 
                          ArrayList helper, 
                          int low, 
                          int middle, 
                          int high,
                          Comparator 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 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?

user_7343513 · Answer

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 personList, Comparator compTr)

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

    ArrayList list = new ArrayList<>();
    for (int i = 0; i < 10; i++) {
        list.add(new Person());
    }
    System.out.println(list);
    mergeSort(list, Comparator.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?

user_4593267 · Answer

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 helper = new ArrayList(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 personList, Comparator compTr) {
    ArrayList helper = new ArrayList(personList);
    mergeSort(personList, helper, 0, personList.size(), compTr);
}

private static void mergeSort(ArrayList list, 
                              ArrayList helper, 
                              int low, 
                              int high, 
                              Comparator 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 list, 
                          ArrayList helper, 
                          int low, 
                          int middle, 
                          int high,
                          Comparator 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++;
    }
}

user_5719229 · Answer

Here is my answer

I changed the code

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

to

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

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

3 Answers