Merge sort with a linked list

Question

I'd like this code reviewed.

import java.util.NoSuchElementException;



public class MergeSort {

    private Node first;
    private Node last;

    private static class Node {
        int element;
        Node next;
        Node(int element, Node node) {
            this.element = element;
            this.next = node;
        }
    }

    public void displayList() {
        Node tempFirst = first;
        while (tempFirst != null) {
            System.out.print(tempFirst.element + " ");
            tempFirst = tempFirst.next;
        }
    }

    public void add (int val) {
        final Node l = last;
        final Node newNode = new Node(val, null);
        last = newNode;
        if (first == null) {
            first = newNode;
        } else {
            l.next = newNode;
        }
    }

    public void sort() {
        /**
         * QQ: should there be an exception check for last == null also ?
         */
        if (first == null) {
            throw new NoSuchElementException("The linkedlist doesnot contain any node.");
        }

        first = divide(first, last);
    }


    private Node getMidPoint(Node node) {
        assert node != null;

        Node fast = node.next;
        Node slow = node;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    } 


    private Node divide(Node node1, Node node2) {
        if (node1 == node2) return node1;

        Node midPoint = getMidPoint(node1);
        Node midpointNext = midPoint.next;
        midPoint.next = null;

        Node n1 = divide(node1, midPoint);
        Node n2 = divide(midpointNext, node2);
        return mergeLinkedList(n1, n2);
    }


    private Node mergeLinkedList(Node node1, Node node2) {
        assert node1 != null;
        assert node2 != null;

        Node current = null;
        Node currentHead = null;

        while (node1 != null && node2 != null) {

            if (node1.element < node2.element) {
                if (current == null) {
                    currentHead = node1;
                    current = node1;
                } else {
                    current.next = node1;
                    current = current.next;
                }
                node1 = node1.next;
            } else {
                if (current == null) {
                    currentHead = node2;
                    current = node2;
                } else {
                    current.next = node2;
                    current = current.next;
                }
                node2 = node2.next;
            }
        }

        current.next = node1 != null ? node1 : node2;

        return currentHead;
    }


    public static void main(String args[]) {
        // odd size list
        MergeSort ms1 = new MergeSort();
        int[] a1 = {5, 4, 3, 2, 1};
        for (int i : a1) {
            ms1.add(i);
        } 
        ms1.sort();
        ms1.displayList();

        System.out.println();

        // even size list.
        MergeSort ms2 = new MergeSort();
        int[] a2 = {5, 4, 3, 2};
        for (int i : a2) {
            ms2.add(i);
        } 
        ms2.sort();
        ms2.displayList();

        System.out.println();

        // list of size 1
        MergeSort ms3 = new MergeSort();
        int[] a3 = {1};
        for (int i : a3) {
            ms3.add(i);
        } 
        ms3.sort();
        ms3.displayList();


        System.out.println();

        // list of size 2
        MergeSort ms4 = new MergeSort();
        int[] a4 = {2, 1};
        for (int i : a4) {
            ms4.add(i);
        } 
        ms4.sort();
        ms4.displayList();


        System.out.println();

    }
}

Answer 1

Starting with some Java API documentation:

public class NoSuchElementException extends RuntimeException

Thrown by the nextElement method of an Enumeration to indicate that there are no more elements in the enumeration.

This is not an Enumeration and you have not called nextElement(). This is not an appropriate exception

sort() should really take a list as a parameter and return a sorted list. Give it a list as a parameter; if a null is passed, Java will do you a nice NullPointerException, free of charge. If the given list is simply empty, return an empty list. Being asked to sort an empty list is not an exceptional error situation. It's no more an error than being asked to sort a list with 1 element, which you do show you can do.

Which brings me to the more important stuff...

Method and object conflated and confused.

You've combined a sorting algorithm with the (hand-rolled) list to be sorted. It would be better to have a properly usable list class and either a mergeSort method on that class or a static helper class with a MergeSort method that can act on any list object. Then you could create a list, examine it to show that it was a well-functioning and populated list, create a mergeSort()-ed version, check that this was a valid list, that it still had all the right elements (none missing, none added or substituted) and that they were in the desired order. You'd have something useful you could do more with.

List object cannot be tested/examined.

This is part of the problem created by the previous issue. There's no way to get at the list data. You print it out on the screen, but it's inaccessible to the rest of your code. What use was the sort? Did it even work? How is this validated except by the naked eye? Since you don't print the unsorted version out on the screen, how does the viewer know you did anything?

Make the list fully usable. Provide a way to traverse and inspect it. Then your code can verify the sort (and do something useful with the sorted data afterwards, if you like).

Printing directly from within the merge class.

Don't do this. Have your class methods return useful values which can be inspected and tested. Print out the results in your main method if you want, but don't litter your classes with println statements.

Final, what?

What do you think you are gaining with those final keywords? Those local variables are going to evaporate when that tiny method returns, so what have you achieved?

I should go on to examine the actual sorting algorithm but I think I'll leave that to somebody else - it's late and I'm tired.