Is generic type ( in this case) being used in more places than needed for this code? I assume that objects include type information needed for compareTo().

The following code is a sub-set of C++ std::list, implemented as a circular double linked list that includes an internal node list where list.next is a reference to the first node, and list.prev is a reference to the last node. list is the equivalent of std::list::end. References to nodes are used instead of std::list::iterator.

There are two implementations of sort. Both use the same merge function that rearranges nodes within a list using the equivalent of std::list::splice() to move one or more nodes at a time. DLList.sort() uses a small array to keep track of sorted run boundaries. DLList.sortr() uses the stack to keep track of sorted run boundaries, and instead of scanning lists to split them, it recursively divides a count (size) by 2 until a base case of size == 1 is reached. Visual Studio 2022 now uses this method in std::list::sort(). On my old desktop with Intel 3770K CPU, both sort methods take about 2 seconds to sort 4,194,304 Integers from sequentially allocated nodes, and about 3 seconds for scattered nodes (tested by refilling sorted list with random numbers and sorting again).

I use one working directory with NetBeans, copying source files to x.java for testing, which is why package x is used.

package x; import java.util.Random; class DLNode<E>{ DLNode<E> next; DLNode<E> prev; E element; DLNode(){ next = null; prev = null; element = null; } DLNode(E e){ next = null; prev = null; element = e; } } class NodePair{ DLNode lft; DLNode end; NodePair(){ lft = null; end = null; } } class DLList<E>{ DLNode<E> list; int size; DLList(){ list = new <E> DLNode(); list.next = list; list.prev = list; size = 0; } public int size() { return size; } public DLNode<E> begin(){ return list.next; } public DLNode<E> end(){ return list; } public E front() { if(size == 0) return null; return (E) list.next.element; } public E back() { if(size == 0) return null; return (E) list.prev.element; } public void push_front(E element) { DLNode<E> node = new DLNode(element); size++; node.next = list.next; node.prev = list; list.next.prev = node; list.next = node; } public void push_back(E element) { DLNode<E> node = new DLNode(element); size++; node.next = list; node.prev = list.prev; list.prev.next = node; list.prev = node; } public E pop_front() { if(size == 0) return null; size--; DLNode<E> node = list.next; DLNode<E> next = node.next; next.prev = list; list.next = next; return (E) node.element; } public E pop_back() { if(size == 0) return null; size--; DLNode<E> node = list.prev; DLNode<E> prev = node.prev; prev.next = list; list.prev = prev; return (E) node.element; } // move rgt node to just before lft node public void splice(DLNode lft, DLNode rgt){ rgt.prev.next = rgt.next; // remove rgt node rgt.next.prev = rgt.prev; rgt.prev = lft.prev; // insert before lft rgt.next = lft; lft.prev.next = rgt; lft.prev = rgt; } // move rgt to end.prev nodes to just before lft node public void splice(DLNode lft, DLNode rgt, DLNode end){ DLNode lst = end.prev; // reference to last node rgt.prev.next = end; // remove rgt nodes end.prev = rgt.prev; rgt.prev = lft.prev; // insert before lft lst.next = lft; lft.prev.next = rgt; lft.prev = lst; } // merge two sorted runs using splice to rearrange nodes within list private <E extends Comparable> DLNode<E> merge(DLNode<E> lft, DLNode<E> rgt, DLNode<E> end){ DLNode<E> nxt; DLNode<E> rtn = lft; // set reference to first merged node if(lft.element.compareTo(rgt.element) > 0) rtn = rgt; while(true){ // merge runs // advance lft until lft > rgt while(lft.element.compareTo(rgt.element) < 1){ lft = lft.next; if(lft == rgt) return rtn; } // advance nxt undil nxt >= lft */ nxt = rgt.next; while(nxt != end && nxt.element.compareTo(lft.element) < 1) nxt = nxt.next; // move rgt to nxt.prev to before lft splice(lft, rgt, nxt); rgt = nxt; if(rgt == end) return rtn; } } // merge sort using array to track sorted run boundaries // anode[i] == run with 2^i nodes or == null // for C++ iterator use std::list::end() instead of null in anode[] @SuppressWarnings("empty-statement") public void sort(){ if(size() < 2) return; final int asz = 32; int i; DLNode anode[] = new DLNode[asz]; // init to null DLNode rgt; DLNode end; DLNode nxt; // create sorted runs, tracking boundaries in anode[] for(end = begin(); end != list;){ rgt = end; nxt = end.next; for(i = 0; i < asz && anode[i] != null; i++){ rgt = merge(anode[i], rgt, nxt); anode[i] = null; } if(i == asz) // don't go past end array i--; anode[i] = rgt; end = nxt; } // merge sorted runs from array to finish sorting list for(i = 0; i < asz && anode[i] == null; i++); rgt = anode[i++]; while(true){ for( ; (i < asz) && anode[i] == null; i++); if(i == asz) return; rgt = merge(anode[i], rgt, end); } } // merge sort using stack to track sorted run boundaries // lft and sz are local, np is one time allocation private NodePair sortr(NodePair np, int sz){ if(sz == 1){ np.end = np.lft.next; return np; } np = sortr(np, sz-sz/2); // lft run DLNode lft = np.lft; np.lft = np.end; // rgt run np = sortr(np, sz/2); np.lft = merge(lft,np.lft,np.end); // merge return np; } public void sortr(){ if(size() < 2) return; NodePair np = new NodePair(); np.lft = list.next; sortr(np, size); } } public class x { public static void main(String[] args) { DLList list = new <Integer> DLList(); final int COUNT = 4*1024*1024; Random r = new Random(); DLNode<Integer> node; Integer i; Integer j; long bgn, end; // test sort with sequentially allocated nodes for(i = 0; i < COUNT; i++) list.push_back((Integer)r.nextInt()); bgn = System.currentTimeMillis(); list.sortr(); end = System.currentTimeMillis(); System.out.println("milliseconds " + (end-bgn)); // test sort with scattered nodes for(node = list.begin(); node != list.end(); node = node.next) node.element = (Integer)r.nextInt(); bgn = System.currentTimeMillis(); list.sortr(); end = System.currentTimeMillis(); System.out.println("milliseconds " + (end-bgn)); // verify sort worked node = list.begin(); i = node.element; j = i; for(node = node.next; node != list.end(); node = node.next){ j = node.element; if(i.compareTo(j) > 0) break; i = j; } if(i.compareTo(j) == 0) System.out.println("passed"); else System.out.println("failed"); // remove all nodes from list while (0 != list.size()) list.pop_front(); } } ```