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.
mergesortImpl()looks funny: why reset everynextreference 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. \$\endgroup\$ – greybeard Jul 28 '16 at 20:32