/**
* Merge Sort implementation and test code for linked lists
* This code includes two implementations of list merging, one recursive and one no-recursive.
* The recursive implementation is limited to about 15000 items.
* This also includes two implementations of the full sorting. One, recursive, the other not.
* The non-recursive one is also known as "bottom up." in this implementation, the non-recursive
* algorithm is slower than the recursive be about a factor of 4.
* @author gtowell
* Created: April 20
* Modified: May 4, 2020
*/
public class MergeSortLL extends SortBase
{
/** The front of the liked list */
Node head = null;
/** The number of items in the COMPLETE list */
int size = 0;
/**
* A simple node in a doubly linked list. Payload is fixed as int
*/
private class Node {
/** The value */
int val;
/** Pointer to the next node */
Node next;
/** Pointer to the previous node */
Node prev;
/**
* Initialized a node
* @param val the payload
*/
public Node(int val)
{
this.val = val;
next=null;
prev=null;
}
}
/**
* A recursive implementation of merging of two sorted lists.
* Works great but limited to merging about 15000 items
* @param a the head of one list
* @param b the head of the other list
* @return the head of the merged lists
*/
private Node sortedMerge(Node a, Node b)
{
Node result = null;
/* Base cases */
if (a == null)
return b;
if (b == null)
return a;
/* Pick either a or b, and recur */
if (a.val <= b.val) {
result = a;
result.next = sortedMerge(a.next, b);
if (result.next!=null)
result.next.prev=result;
}
else {
result = b;
result.next = sortedMerge(a, b.next);
if (result.next!=null)
result.next.prev=result;
}
return result;
}
/**
* A non-recursive implementation of merging two lists.
* This can handle arbitrary length lists
* @param a the head of one list
* @param b the head of the other list
* @return the head of the merged lists
*/
private Node sortedMergeNR(Node a, Node b)
{
Node result = null;
Node tail = null;
/* Base cases */
if (a == null)
return b;
if (b == null)
return a;
while (a!=null && b!=null)
{
if (a.val <= b.val) {
if (result==null)
{
result = a;
tail=a;
}
else
{
tail.next = a;
a.prev=tail;
tail=a;
}
a=a.next;
}
else {
if (result==null)
{
result = b;
tail=b;
}
else
{
tail.next=b;
b.prev=tail;
tail=b;
}
b=b.next;
}
}
if (a!=null) {
tail.next=a;
a.prev=tail;
}
if (b!=null) {
tail.next=b;
b.prev=tail;
}
return result;
}
/**
* A "bottom up" non-recursive implementation of mergesort. This implementation is
* stunningly inefficient; it is still O(nlogn) but it is about a factor of 4 slower than the
* recursive implementation in this code. With some work, it could be made far mode efficient.
* In particular, list splitting could be done better. The tacking merges together could also
* be improved. But it works.
* With some work could pass lengths into the merge method and thereby avoid several list traversals.
* This is "bottom up" in the sense that it starts with lists of size 1, merges them, etc.
*
* @param h the head of the list to be sorted
* @return the head of the sorted list.
*/
private Node mergeSortBottomUp(Node h)
{
// Base case : if head is null
if (h == null || h.next == null) {
return h;
}
Node head=h;
Node prevPart=null;
for (int step=1; step