Merge sorting a singly-linked list in Java

Question

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 <E> the type of the datum hold by this node. 
 */
 public static final class LinkedListNode<E> {
 private final E datum;
 private LinkedListNode<E> next;
 public LinkedListNode(final E datum) {
 this.datum = datum;
 }
 public E getDatum() {
 return datum;
 }
 public LinkedListNode<E> getNext() {
 return next;
 }
 public void setNext(final LinkedListNode<E> node) {
 this.next = node;
 }
 }
 public static <E extends Comparable<? super E>>
 LinkedListNode<E> mergesort(final LinkedListNode<E> head) {
 if (head == null || head.getNext() == null) {
 return head;
 }
 return mergesortImpl(head);
 }
 private static <E extends Comparable<? super E>>
 LinkedListNode<E> mergesortImpl(final LinkedListNode<E> head) {
 if (head.getNext() == null) {
 return head;
 }
 final LinkedListNode<E> leftSublistHead = head;
 final LinkedListNode<E> rightSublistHead = head.getNext();
 LinkedListNode<E> leftSublistTail = leftSublistHead;
 LinkedListNode<E> rightSublistTail = rightSublistHead;
 LinkedListNode<E> 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;
 left = false;
 } else {
 rightSublistTail.setNext(currentNode);
 rightSublistTail = currentNode;
 left = true;
 }
 currentNode = currentNode.getNext();
 }
 leftSublistTail.setNext(null);
 rightSublistTail.setNext(null);
 return merge(mergesortImpl(leftSublistHead),
 mergesortImpl(rightSublistHead));
 }
 private static <E extends Comparable<? super E>>
 LinkedListNode<E> merge(LinkedListNode<E> leftSortedListHead,
 LinkedListNode<E> rightSortedListHead) {
 LinkedListNode<E> mergedListHead;
 LinkedListNode<E> mergedListTail;
 if (rightSortedListHead.getDatum()
 .compareTo(leftSortedListHead.getDatum()) < 0) {
 mergedListHead = rightSortedListHead;
 mergedListTail = rightSortedListHead;
 rightSortedListHead = rightSortedListHead.getNext();
 } else {
 mergedListHead = leftSortedListHead;
 mergedListTail = leftSortedListHead;
 leftSortedListHead = leftSortedListHead.getNext();
 }
 while (leftSortedListHead != null && rightSortedListHead != null) {
 if (rightSortedListHead
 .getDatum()
 .compareTo(leftSortedListHead.getDatum()) < 0) {
 mergedListTail.setNext(rightSortedListHead);
 mergedListTail = rightSortedListHead;
 rightSortedListHead = rightSortedListHead.getNext();
 } else {
 mergedListTail.setNext(leftSortedListHead);
 mergedListTail = leftSortedListHead;
 leftSortedListHead = leftSortedListHead.getNext();
 }
 }
 while (leftSortedListHead != null) {
 mergedListTail.setNext(leftSortedListHead);
 mergedListTail = leftSortedListHead;
 leftSortedListHead = leftSortedListHead.getNext();
 }
 while (rightSortedListHead != null) {
 mergedListTail.setNext(rightSortedListHead);
 mergedListTail = rightSortedListHead;
 rightSortedListHead = rightSortedListHead.getNext();
 }
 return mergedListHead;
 }
 public static <E> String toString(LinkedListNode<E> head) {
 final StringBuilder sb = new StringBuilder();
 while (head != null) {
 sb.append(head.getDatum()).append(' ');
 head = head.getNext();
 }
 return sb.toString();
 }
 private static LinkedListNode<Integer> 
 createRandomLinkedList(final int size, final Random random) {
 if (size == 0) {
 return null;
 }
 LinkedListNode<Integer> head = new LinkedListNode<>(
 random.nextInt(100));
 LinkedListNode<Integer> tail = head;
 for (int i = 1; i < size; ++i) {
 final LinkedListNode<Integer> newnode = 
 new LinkedListNode<>(random.nextInt(100));
 tail.setNext(newnode);
 tail = newnode;
 }
 return head;
 }
 public static void main(final String... args) {
 final long seed = System.nanoTime();
 final Random random = new Random(seed);
 LinkedListNode<Integer> head = createRandomLinkedList(10, random);
 System.out.println("Seed = " + seed);
 System.out.println(toString(head));
 head = mergesort(head);
 System.out.println(toString(head));
 }
}

As always, any critique is much appreciated.

• greybeard: From just skimming, the split open coded into mergesortImpl() looks funny: why reset every next reference ld(n) times? For each split, just run the list: one reference advances by two nodes (if possible), the other - mid would seem an appropriate name - by one. When the fast reference hits the end, mid will reference the middle of the list: take mid.getNext()` as the second list; mid.setNext(null) should ready the parameter list as the first list.
• greybeard: (Or even pass the list length ... and split after half of it.)
• coderodde: @greybeard I don't get what you are proposing. Please consider giving an answer with concrete code.

Answer 1

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.

• JS1: There isn't a bug because both left and right lists are already sorted before being passed to the merge() function.
• forsvarir: @JS1 of course it is, that'll be the recursive call. I'm sure there's a lesson there about rereading the code when I come back to it, rather than just working from what I remember of it. Thanks.

Answer 2

The idea to split the input list is uncalled for - when merging begins with runs of length 1, begin by taking items from the input one by one.
Posting this mostly to illustrate my comments about how to split (defaulting on the counting variant - would have a different interface and look tedious as well as boring (and pointless: see introductory remark): keep account of list lengths in mergeSort(Impl). Pass a count into split(), return node after that count and terminate head at the node.)
If there was value in putting items in one of two lists alternately, have a look at Alternator.
Without giving it due diligence:

public static class LinkedList<E> {
 /** Splits the input linked list into two smaller linked lists. */
 public interface Splitter<E> {
 /** Splits the input linked list into two smaller linked lists.
 * {@code head} and {@code head.getNext()} better not be {@code null}.
 * @return The node that starts the other sublist. */
 Node<E> split(Node<E> head);
 }
/** A node in a singly-linked list.
 * 
 * @param <E> the type of the datum hold by this node. 
 */
 public static class Node<E> {
 private final E datum;
 private Node<E> next;
 public Node(final E datum) {
 this.datum = datum;
 }
 public E getDatum() { return datum; }
 public Node<E> getNext() { return next; }
 public Node<E> setNext(final Node<E> node) {
 return this.next = node;
 }
 }
 Node<E> node;
 public LinkedList(Node<E> node) {
 this.node = node;
 }
// to make merge look deceivingly simple
 E getDatum() { return node.getDatum(); }
 long estimateSize() {
 long count = 0;
 for (Node<E> n = node ; null != n ; n = n.getNext())
 count++;
 return count;
 }
}
static LinkedList.Splitter theOne = new HackerAndCoder<>();
static LinkedList.Node split(LinkedList.Node head) {
 return theOne.split(head);
}
static class Alternator<E> implements LinkedList.Splitter<E> {
@Override
/** Splits the input linked list into two smaller linked lists.
* {@code head} and {@code head.getNext()} better not be {@code null}.
* @return The node that starts the other sublist. */
 public LinkedList.Node<E>
 split(final LinkedList.Node<E> head) {
 // second list will start with second node
 final LinkedList.Node<E> rightSublistHead;
 LinkedList.Node<E> n3,
 n1 = head,
 n2 = rightSublistHead = head.getNext();
 do {
 // replace next by next-but-one
 n1.setNext(n3 = n2.getNext());
 n1 = n2;
 } while (null != (n2 = n3));
 n1.setNext(null);
 return rightSublistHead;
 }
}
public static <E extends Comparable<? super E>>
LinkedList.Node<E> mergesort(final LinkedList.Node<E> head) {
 if (head == null || head.getNext() == null) {
 return head;
 }
 return mergesortImpl(head);
}
private static <E extends Comparable<? super E>>
LinkedList.Node<E> mergesortImpl(final LinkedList.Node<E> head) {
 return null == head || null == head.getNext() ? head
 : merge(mergesortImpl(split(head)),
 mergesortImpl(head));
}
/** Splits the input linked list into two smaller linked lists.
* @return The node that starts the other sublist. */
static <E extends Comparable<? super E>> LinkedList.Node<E>
split1(final LinkedList.Node<E> head) {
 final LinkedList.Node<E> rightSublistHead = head.getNext();
 LinkedList.Node<E>
 currentNode,
 nextNode,
 leftSublistTail = head,
 rightSublistTail = nextNode = rightSublistHead;
 for (boolean left = false ; null != (currentNode = nextNode) ;
 left = !left) {
 nextNode = currentNode.getNext();
 (left ? leftSublistTail : rightSublistTail)
 .setNext(currentNode);
 if (left)
 leftSublistTail = currentNode;
 else
 rightSublistTail = currentNode;
 }
 leftSublistTail.setNext(null);
 rightSublistTail.setNext(null);
 return rightSublistHead;
}
/** Splits the input linked list into two smaller linked lists.
* {@code head} and {@code head.getNext()} better not be {@code null}.
* @return The node that starts the other sublist. */
static <E extends Comparable<? super E>> LinkedList.Node<E>
split2(final LinkedList.Node<E> head) {
// second list will start with second node
 final LinkedList.Node<E> rightSublistHead;
 LinkedList.Node<E> n3,
 n1 = head,
 n2 = rightSublistHead = head.getNext();
 do {
 // replace next by next-but-one
 n1.setNext(n3 = n2.getNext());
 n1 = n2;
 } while (null != (n2 = n3));
 n1.setNext(null);
 return rightSublistHead;
}
static class HackerAndCoder<E> implements LinkedList.Splitter<E> {
/** Splits the input linked list into two smaller linked lists.
* {@code head} better not be {@code null}.
* @return The node that starts the other sublist. */
 @Override
 public LinkedList.Node<E>
 split(LinkedList.Node<E> head) {
 LinkedList.Node<E> mid = head,
 fast = head.getNext();
 while (null != (fast = fast.getNext())
 && null != (fast = fast.getNext())) 
 mid = mid.getNext();
 head = mid.getNext();
 mid.setNext(null);
 return head;
 }
}
private static <E extends Comparable<? super E>>
LinkedList.Node<E> merge(LinkedList.Node<E> leftSorted,
 LinkedList.Node<E> rightSorted) {
// left & right will be modified:
// need to be new lists/(shallow)clones
// even if parameters changed to LinkedList
 LinkedList<E>
 left = new LinkedList<>(leftSorted),
 right = new LinkedList<>(rightSorted),
 chosen = (left.getDatum().compareTo(right.getDatum()) < 0)
 ? left : right;
 LinkedList.Node<E>
 merged,
 tail = merged = chosen.node;
 while (null != (chosen.node = chosen.node.getNext())) {
 chosen = (left.getDatum().compareTo(right.getDatum()) < 0)
 ? left : right;
 tail = tail.setNext(chosen.node);
 }
 tail.setNext((chosen == left ? right : left).node);
 return merged;
}