Merge sorting a singly-linked list in Java

I have this nifty merge sort implementation for sorting singly-linked lists. Its running time is \$\Theta(n \log n)\$, yet it uses only \$\Theta(\log n)\$ space (the stack). See what I have below.

ListMergesort.java:

```
package net.coderodde.fun;

import java.util.Random;

/**
* This class contains a method for sorting a singly-linked list.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Jul 28, 2016)
*/
public class ListMergesort {

/**
* This class implements a node in a singly-linked list.
*
* @param the type of the datum hold by this node.
*/
public static final class LinkedListNode {

private final E datum;
private LinkedListNode next;

public LinkedListNode(final E datum) {
this.datum = datum;
}

public E getDatum() {
return datum;
}

public LinkedListNode getNext() {
return next;
}

public void setNext(final LinkedListNode node) {
this.next = node;
}
}

public static >
LinkedListNode mergesort(final LinkedListNode head) {
if (head == null || head.getNext() == null) {
return head;
}

return mergesortImpl(head);
}

private static >
LinkedListNode mergesortImpl(final LinkedListNode head) {
if (head.getNext() == null) {
return head;
}

final LinkedListNode leftSublistHead = head;
final LinkedListNode rightSublistHead = head.getNext();

LinkedListNode leftSublistTail = leftSublistHead;
LinkedListNode rightSublistTail = rightSublistHead;

LinkedListNode currentNode = rightSublistHead.getNext();
boolean left = true;

// Split the input linked list into two smaller linked lists:
while (currentNode != null) {
if (left) {
leftSublistTail.setNext(currentNode);
leftSublistTail = currentNode;
l

On the whole, I like your approach and found it very easy to follow. There are a few things to consider though.

TestHarness

I don't like having main methods in classes as test harnesses. I would prefer to either see JUnit tests, or for some kind of MergeSortTestHarness to contain the method that exercises your class. This creates a separation between the code that does the work and the code that exercises it. It also forces you to use the public interface to the class. At the moment, you've got ListMergesort which presents generic methods and contains a generic LinkedListNode class, but has a private method that's called by main that creates a random list of integers. This method clearly doesn't belong.

Variable Naming

When I first saw this code in toString, I thought it was going to be a bug:

head = head.getNext();

It looks like it's updating the head of the list as it iterates through to print. It's not of course, it's using a local variable that's actually iterating along the list. The name is a bit misleading, current or iter or something suggesting that it's expected to move along the list might be better.

left = !left

At the end of your split loop you can do:

left = !left;
currentNode = currentNode.getNext();

This would allow you to remove the assignments from the split clauses above to make it more concise.

Copy to end

You stop merging the lists after you've identified that one of the input streams is empty. At which point you copy the rest of the list across like this:

while (leftSortedListHead != null) {
    mergedListTail.setNext(leftSortedListHead);
    mergedListTail = leftSortedListHead;
    leftSortedListHead = leftSortedListHead.getNext();
}

It feels a lot like at this point all you actually have to do is:

if(leftSortedListHead != null) {
    mergedListTail.setNext(leftSortedListHead);
} else if(rightSortedListHead != null) {
    mergedListTail.setNext(rightSortedListHead);
}

Each of the input lists is already a null terminated list and you don't need mergedListTail after this point, since you return the head, so you can just tack the rest of the input list onto the end.

StackExchange Code Review Q#136224, answer score: 4