# 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<T extends Comparable<T>> implements Iterable<T> {

}

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

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

/*******************************************************
*
*
********************************************************/
}

/*******************************************************
*
*
********************************************************/
}

int mid = totalNumberOfElements / 2;

Node<T> right = null;

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

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

}

private Node<T> merge(Node<T> left, Node<T> right) {
Node<T> leftNode = left;
Node<T> rightNode = right;

Node<T> duplicateHead = new Node<T>(null, null);

while (leftNode != null || rightNode != null) {

if (leftNode == null) {
currentNode.next = new Node<T>(rightNode.data, null);
rightNode = rightNode.next;
currentNode = currentNode.next;

} else if (rightNode == null) {
currentNode.next = new Node<T>(leftNode.data, null);
leftNode = leftNode.next;
currentNode = currentNode.next;

} else {
if (compare(leftNode.data, rightNode.data) < 0) {
currentNode.next = new Node<T>(leftNode.data, null);
leftNode = leftNode.next;
currentNode = currentNode.next;

} else if (compare(leftNode.data, rightNode.data) == 0) {
currentNode.next = new Node<T>(leftNode.data, null);
currentNode.next.next = new Node<T>(rightNode.data, null);
currentNode = currentNode.next.next;
leftNode = leftNode.next;
rightNode = rightNode.next;

} else {
currentNode.next = new Node<T>(rightNode.data, null);
rightNode = rightNode.next;
currentNode = currentNode.next;
}
}
}

}

int count = 0;
count++;
}
return count;
}

private int compare(T a, T b) {
return a.compareTo(b);
}

/*******************************************************
*
* node class
*
********************************************************/
private static class Node<T> {
private T data;
private Node<T> next;

public Node(T data, Node<T> next) {
this.data = data;
this.next = next;
}
}

/*******************************************************
*
* iterator class
*
********************************************************/
@Override
public Iterator<T> iterator() {
}

private class LinkedListIterator implements Iterator<T> {

private Node<T> temp;

}

@Override
public boolean hasNext() {
return temp != null;
}

@Override
public T next() {
if (!hasNext())
throw new NoSuchElementException();
T item = temp.data;
temp = temp.next;
return item;
}
}

public static void main(String[] args) {
System.out.println(list1);

System.out.println(list1);
}
}


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<T> 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<T> linkedList)


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()) {
}


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.