Sorting a linked list using mergesort

This sorts a linked list using mergegort. Can you please critique my code and provide your thoughts on where I should improve my code?

```
import java.util.Iterator;
import java.util.NoSuchElementException;

public class LinkedList> implements Iterable {

private Node head;

public LinkedList() {
head = null;
}

@Override
public String toString() {
StringBuffer result = new StringBuffer();

for (Iterator i = this.iterator(); i.hasNext();) {
result.append((Object) i.next() + " ");
}
return result.toString();
}

/*
*
* add first element
*
/
public void addFirst(T item) {
head = new Node(item, head);
}

/*
*
* merge sort linked list
*
/
public void mergeSortLinkedList(LinkedList linkedList) {
head = sortLinkedList(linkedList.head);
}

private Node sortLinkedList(Node head) {

if (head == null || head.next == null)
return head;

int totalNumberOfElements = getCount(head);

int mid = totalNumberOfElements / 2;

Node currentNode = head;
Node left = head;
Node right = null;

int countHalf = 0;
while (currentNode != null) {
countHalf++;
Node next = currentNode.next;

if (countHalf == mid) {
currentNode.next = null;
right = next;
}
currentNode = next;
}

Node leftHalf = sortLinkedList(left);
Node rightHalf = sortLinkedList(right);
Node mergedLinkedList = merge(leftHalf, rightHalf);

return mergedLinkedList;
}

private Node merge(Node left, Node right) {
Node leftNode = left;

First of all you should use StringBuilder, not StringBuffer. Unless you have a good reason in a multithreading environment, then you probably could use StringBuffer. (Just replace the class names, everything else stays the same).

I think this is a exercise for university. So I divide my review in two parts. First I don't ask 'why' on many places, then I ask 'why' ;-)

The algorithm seems to be fine to me. I found only one hidden bug, but the bug has nothing to do with the merge sort:

The signature of this method seems to be strange to me:

public void mergeSortLinkedList(LinkedList linkedList)

You have a linked list, you call this method of the linked list and have to give it a linked list. For me this looks like you can merge two lists together and then sort the result... merge, sort... not the behavior you want to express.

But what happens if you call this method this way:

userNameList.mergeSortLinkedList( addressList );

Now the userNameList will contain addresses in sorted order, but addressList is unchanged.

I think you have to change the signature and there are two choices:

public static void mergeSortLinkedList(LinkedList linkedList)
public void mergeSortLinkedList()

and maybe you shouldn't call it mergeSortLinkedList(). It is a method of a LinkedList, so you could call it mergeSort() but the used algorithm is a implementation detail, so sort() would be enough (you could explain the used algorithm in the documentation comment above the method, which is missing right now).

I like the merge() method. You can see the functionality in a second. The only thing: you get two parameters, assign them to two variables and ignore the parameters after this. You don't need those two variables, you can simply use the parameters.

Now the 'why' part:

Why did you reinvented the LinkedList? There is a java.util.LinkedList. If this is an exercise, you have to, ok.

Why didn't you implement simple accessor and manipulation methods like get(int index), remove(int index) (or removeFirst because of your addFirst), isEmpty() and so on. Together with a sublist(int start, int length) you could do implement merge sort on a higher level.

Then you have to operate on the LinkedList instead of Nodes. But in merge() you can do something like this to move an element:

if (left.isEmpty()) {
    mergedList.addFirst(right.removeFirst());
}

or removeLast() to get the ordering right.

Why do you add new elements at the head? It'll me more natural when you add it at the tail of the list.

Why did you implement an iterator? In your case you didn't really need it.

A performance hints:

the sortLinkedList should take the length of the list as parameter. Then you don't have to count the number of elements of each (sub-) list each time, and for the recursive calls of sortLinkedList you can calculate the lengths of the sublists.

You can see the difference by executing the sort method 1.000.000 times in a for loop and measuring the elapsed time with System.currentTimeMillis(). Even though you gonna sort a sorted list, you will see a difference.

StackExchange Code Review Q#101625, answer score: 2