MergeSorting LinkedList in Java recursively

Question

So the task is to implement a linked-list and merge-sort which sorts linked-lists. I am fully aware that in industry I most likely won't have to implement any of these but I feel it's a good way to practice Java. Here is what I've got up to this point:

Node class:

public class Node<E extends Comparable<E>>
    {

    public E data;
    public Node<E> next;

    public Node(E data)
    {
        this.data = data;
        next = null;
    }

    public void printData()
    {
        System.out.print(data + " ");
    }
}

LinkedList class:

public class LinkedList<E extends Comparable<E>>
{

    protected Node<E> root;
    protected int size = 0;

    public LinkedList()
    {
        root = null;
    }


    public void addBeg(E e)
    {

        Node<E> newNode = new Node<E>(e);
        newNode.next = root;
        root = newNode;

        size++;
    }

    public Node deleteBeg()
    {
        Node<E> temp = root;
        if(!isEmpty())
        {
            root = root.next; 
            size--;
        }
        return temp;
    }

    public void setRoot(Node<E> newRoot)
    {
        root = newRoot;
    }

    public boolean isEmpty()
    {
        return root == null;
    }

    public Node<E> getRoot()
    {
        return root;
    }

    public void printList()
    {
        Node<E> cur = root;   
        while(cur!=null)
            {
                cur.printData();
                cur=cur.next;
            }
        System.out.println();        
    }
}

MergeSorter Class:

public class MergeSorter<E extends Comparable<E>>
{

    public MergeSorter()
    {

    }

    private void split(LinkedList<E> list, LinkedList<E> firHalf, LinkedList<E> secHalf)
    {
        //if 0 or only 1 elements in the list - it doesn't seem to work, however
        if(list.getRoot() == null || list.getRoot().next == null)firHalf = list;
        else{
            Node<E> slow = list.getRoot(); 
            Node<E> fast = list.getRoot().next; 
            while(fast!=null)
            {
                fast = fast.next;
                if(fast!=null)
                {
                    fast = fast.next;
                    slow = slow.next;
                } 
            }
            //If I use the following line firHalf list is empty when in the caller of this method (it's not in this method, however). Don't understand why ):
            //firHalf = list; 
            firHalf.setRoot(list.getRoot());
            secHalf.setRoot(slow.next);
            slow.next = null;
        }

    }



    private LinkedList<E> merge(LinkedList<E> a, LinkedList<E> b)
     {
        LinkedList<E> mergedList = new LinkedList<E>();    
        Node<E> dummy = new Node<E>(null);
        Node<E> tail = dummy;

        while(true)
        {         
            if(a.getRoot() == null){
                tail.next = b.getRoot();
                break;
            }
            else if(b.getRoot() == null){
                tail.next = a.getRoot();
                break;
            }

            else 
            {
                if(a.getRoot().data.compareTo(b.getRoot().data) <= 0)
                {
                    tail.next = a.getRoot();
                    tail = tail.next;
                    a.setRoot(a.getRoot().next);
                }

                else
                {   
                    tail.next = b.getRoot();
                    tail = tail.next;
                    b.setRoot(b.getRoot().next);
                }
                tail.next = null;
            }

        }
        mergedList.setRoot(dummy.next);
        return mergedList;
    }

    public void mergeSort(LinkedList<E> list)
    {
        Node<E> root = list.getRoot();
        LinkedList<E> left  = new LinkedList<E>();
        LinkedList<E> right = new LinkedList<E>();

        if(root == null || root.next == null) return; //base case
        split(list, left, right); //split

        mergeSort(left);
        mergeSort(right);

        list = merge(left, right); // when this mergeSort returns this list should be  
                                   // referenced by the left or right variable of the 
                                   // current mergeSort call (but it isn't!)
    }
}

I am fairly new to Java (coming from a C background) so I am sincerely sorry in advance if my code is utterly false. When I test the split and merge methods in the MergeSorter class independently, everything seems to work (splitting a list consisting of 0 or 1 element is not working and is driving me crazy but this is not needed for merge-sorting). The mergeSort method, however, is not working and I can't seem to figure out way. I tried to debug it myself and there's seems to be a problem when two halves are merged into one list and then the recursion returns. The newly merged list should be referenced by either the left or right variable of the current mergeSort call but instead I get only the last element instead of the whole list.

Answer 1

Method arguments in Java are always passed by value.

This can be a bit confusing, since objects are always accessed via references, so you might think they're passed by reference; but they're not. Rather, the references are passed by value.

What this means is, a method like this:

public void methodThatDoesNothing(Object dst, Object src) {
    src = dst;
}

actually does nothing. It modifies its local variable src to refer to the same object as the local variable dst, but those are just local variables that disappear when the function returns. They're completely separate from whatever variables or expressions were passed into the method.

So, in your code, this:

firHalf = list;

does not really do anything. I guess what you want is:

while (! firHalf.isEmpty()) {
    firHalf.deleteBeg();
}
if (! list.isEmpty()) {
    firHalf.addBeg(list.root().data);
}

which modifies the objected referred to by firHalf so it has the same zero-or-one elements as list.