CODEWITHSUNDEEP
javalistmergesort
mottese
mottese

Reputation: 302

Merge Sorting in Java

I have a class that does some recursive merge sorting on a generic List, as long as the element implement Comparable. I have a void method called mergeSort(List toSort), and a method mergeSortedLists(List left, List right) that takes two lists that have already been sorted, and then combines them into one sorted list. The problem is, the mergeSort(...) method doesn't seem to be manipulating the toSort variable. Well it is, but the changes don't show after it jumps up a level. Here are the sorting methods:

public static <E extends Comparable<E>> void mergeSort(List<E> toSort)
{
  if(toSort.size() > 1)
  {
    List<E> temp = toSort.subList(0, toSort.size()/2);

    ArrayList<E> left = new ArrayList<E>(0);
      for(E e : temp) left.add(e);

    temp = toSort.subList(toSort.size()/2, toSort.size());

    ArrayList<E> right = new ArrayList<E>(0);
      for(E e : temp) right.add(e);

    if(right.size() != 1) mergeSort(right);
    if(left.size() != 1) mergeSort(left);

    toSort = mergeSortedLists(left, right);
  }
}


public static <E extends Comparable<E>> List<E> mergeSortedLists(List<E> leftList, List<E> rightList)
{
  ArrayList<E> list = new ArrayList<E>();

  while(!leftList.isEmpty() && !rightList.isEmpty())
  {
    if((leftList.get(0)).compareTo(rightList.get(0)) <= 0)
      list.add(leftList.remove(0));

    else
      list.add(rightList.remove(0));
  }

  while(!leftList.isEmpty())
    list.add(leftList.remove(0));

  while(!rightList.isEmpty())
    list.add(rightList.remove(0));

  return list;
}

I normally have print statements for error checking, and those show that mergeSortedLists(...) sorts correctly and returns the correct list. Then, I assign the toSort variable in mergeSort(...) to whatever mergeSortedLists(...) returns. That assignment works. Now, it jumps back up a level to combine that list with a different list, and the changes seem to be lost. I have no clue what is happening.

Upvotes: 1

Views: 1563

Answers (2)

Attila
Attila

Reputation: 28762

Instead of this

toSort = mergeSortedLists(left, right);

try

toSort.clear();
toSort.addAll(mergeSortedLists(left, right));

The problem with your approach is that you reset the reference to the list, but that does not propagate back to the original function. The suggested version manipulates the original list that you were given the reference to. Since you don't change the reference, the changes to the original list will show up at the caller after the function returns.

To clarify: when you pass an argument to a function, a copy of that argument is created that functions as the local variable within the function. When you make changes to the value of that variable itself, those changes are made to the copy and not to the original (from which the copy was made when the function is called). In the suggested version, the copy is a reference, so altohugh the reference is copied, the object (here: list) is not, so the two rerefrences point to the same object. Thus changes made to the object via the copy (local variable), "show up" when the function returns.

Upvotes: 1

Stuart Golodetz
Stuart Golodetz

Reputation: 20616

Parameters (even references to objects!) are passed by value in Java, so you're modifying the local copy of toSort, not the one in the calling function. One way of getting around this would be to return the list you pass in again, i.e.

public static <E extends Comparable<E>> List<E> mergeSort(List<E> toSort)

Then you'd say things like:

right = mergeSort(right);

etc., and return using:

return mergeSortedLists(left, right);

I haven't thoroughly read through the rest of the code, but hopefully that should get you on the right lines :)

Upvotes: 1

Related Questions