Merge Sorting in Java

Question

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.

Attila · Accepted Answer · 2012-04-26 23:46:25Z

1

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.

edited Apr 26, 2012 at 23:46

answered Apr 26, 2012 at 23:36

Attila

28.9k3 gold badges50 silver badges58 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Stuart Golodetz Over a year ago

@user1359900: For the reason I mentioned in my answer (and Attila is alluding to) - parameter-passing in Java is always by value, not by reference. Here's a reasonable-looking link (please ignore the title though, I'm not posting it in a pointed way): javadude.com/articles/passbyvalue.htm

Stuart Golodetz Over a year ago

The essential point is that given that parameter-passing is by value in Java, you need to find a way to modify the original list. Attila's approach is to work with the original list via the reference that's passed in rather than trying to create a new list; the approach I gave is to create a new list but return it so that it can be assigned over the original list. Both will work in this instance. (That wouldn't be true if you were working with immutable lists - in that case you'd have to go for the return approach.) I guess Attila's approach is more imperative, mine's more functional.

Stuart Golodetz · Accepted Answer · 2012-04-26 23:38:59Z

1

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 :)

edited Apr 26, 2012 at 23:38

answered Apr 26, 2012 at 23:32

Stuart Golodetz

20.7k4 gold badges55 silver badges81 bronze badges

Collectives™ on Stack Overflow

Merge Sorting in Java

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related