merge sort list java

Question

The output of this code is always the last digit of the input. Cannot find the reason.I use merge sort recursively, and the result is wrong. I thought maybe the list being overlapped.

public class MergeSort {
    public static List<Integer> Sort(List<Integer> list) {
        if (list.size() <= 1) {
            return list;
        }
        List<Integer> aList = new ArrayList<Integer>();
        aList = list.subList(0, list.size() / 2);

        List<Integer> bList = new ArrayList<Integer>();
        bList = list.subList(list.size() / 2, list.size());

        Sort(aList);
        Sort(bList);

        merge(aList, bList, list);
        return list;
    }

    private static List<Integer> merge(List<Integer> alist,
        List<Integer> blist, List<Integer> list) {
        int alistIndex = 0, blistIndex = 0, listIndex = 0;
        while (alistIndex < alist.size() && blistIndex < blist.size()) {
            if (alist.get(alistIndex) < blist.get(blistIndex)) {
                list.set(listIndex, alist.get(alistIndex));
                alistIndex++;
            } else {
                list.set(listIndex, blist.get(blistIndex));
                blistIndex++;
            }
            listIndex++;
        }
        List<Integer> rest;
        if (alistIndex == alist.size()) {
            rest = blist.subList(blistIndex, blist.size());
            for(int c = blistIndex; c < rest.size(); c++){
                list.set(listIndex, blist.get(c));
                listIndex++;
            }
        } else {
            rest = alist.subList(alistIndex, alist.size());
            for(int c = alistIndex; c < rest.size(); c++){
                list.set(listIndex, alist.get(c));
                listIndex++;
            }
        }
        return list;
    }
}

The test input is 5, 4, 3, 2, 1. But the output is 1, 1, 1, 1, 1. So, there must have some wrong with this merge method

Answer 1

The quick fix to your problem is replacing:

List<Integer> aList = new ArrayList<Integer>();
aList = list.subList(0, list.size() / 2);

List<Integer> bList = new ArrayList<Integer>();
bList = list.subList(list.size() / 2, list.size());

with:

List<Integer> aList = new ArrayList<Integer>(list.subList(0, list.size() / 2));
List<Integer> bList = new ArrayList<Integer>(list.subList(list.size() / 2, list.size()));

You create new ArrayLists for your partitions then immediately change the reference to a view of your original list.

---

The partitioning of the list is being done correctly, however, because you are using the view instead of the shallow copies, during the merge you are changing your partitions.

Usually if you are doing a sort that mutates the original list, you don't return anything from that method, so something like:

public class MergeSort {
  public static void sort(List<Integer> list) {
    if (list.size() < 2) {
      return;
    }
    int mid = list.size()/2;
    List<Integer> left = new ArrayList<Integer>(list.subList(0, mid));
    List<Integer> right = new ArrayList<Integer>(mid, list.size()));

    sort(left);
    sort(right);
    merge(left, right, list);
  }

  private static void merge(
      List<Integer> left, List<Integer> right, List<Integer> list) {
    int leftIndex = 0;
    int rightIndex = 0;
    int listIndex = 0;

    while (leftIndex < left.size() && rightIndex < right.size()) {
      if (left.get(leftIndex) < right.get(rightIndex)) {
        list.set(listIndex++, left.get(leftIndex++));
      } else {
        list.set(listIndex++, right.get(rightIndex++));
      }
    }
    while (leftIndex < left.size()) {
      list.set(listIndex++, left.get(leftIndex++));
    }
    while (rightIndex < right.size()) {
      list.set(listIndex++, right.get(rightIndex++));
    }
  }
}

---

The alternative where the original list isn't mutated could be:

public class MergeSort {
  public static List<Integer> sorted(List<Integer> list) {
    if (list.size() < 2) {
      return list;
    }
    int mid = list.size()/2;
    return merged(
        sorted(list.subList(0, mid)), 
        sorted(list.subList(mid, list.size())));
  }

  private static List<Integer> merged(List<Integer> left, List<Integer> right) {
    int leftIndex = 0;
    int rightIndex = 0;
    List<Integer> merged = new ArrayList<Integer>();

    while (leftIndex < left.size() && rightIndex < right.size()) {
      if (left.get(leftIndex) < right.get(rightIndex)) {
        merged.add(left.get(leftIndex++));
      } else {
        merged.add(right.get(rightIndex++));
      }
    }
    merged.addAll(left.subList(leftIndex, left.size()));
    merged.addAll(right.subList(rightIndex, right.size()));
    return merged;
  }
}

Answer 2

The subList method creates a new list from the original one, but still holds a reference to the original elements, such that any change made in the first will affect the second and vice-versa. In your merge method, you are overwriting your original list and at the same time changing the greater elements in the sublist that do not pass your if condition. Please refer to for this post more information on the matter