Adaptive counting sort for integer arrays in Java

(See the next iteration.)

I have this adaptive counting sort for integer arrays. Basically, it maintains a doubly-linked list of nodes. Each node knows its integer \$a_i\$ and contains the counter describing the number of \$a_i\$ encountered so far in the range. As you might know, the running time of counting sort is \$\mathcal{O}(n + k)\$, where \$k = \max a_i - \min a_i\$ is the "width" of the input array, which limits its applicability in general case. The linked list structure allows sorting even for large values of \$k\$. Also, as an optimization, the adaptive version knows the previous node incremented, which allows it to adapt to "closeness" of integers in the array.

The running time, in my opinion, varies between \$\Omega(n)\$ and \$\mathcal{O}(n^2)\$, although I don't have a formal proof. The space requirements are, however, easy to calculate: its the amount of distinct integers in the requested range.

As that adaptive sort seems to have quadratic running time in the worst case, I don't hope it to be comparable to java.util.Arrays.sort(int[]).
The included demonstration, however, compares my sort against an optimized insertion sort (called "straight insertion sort" as far as I can remember) that minimizes the number of assignments. I won't include all information that the included demonstration prints, but the total running time is of order:

Total insertion sort time: 29091 milliseconds.
Total counting sort time: 4595 milliseconds.


In the demo, I considered two types of arrays: arrays with small number of distinct elements, and presorted arrays with small number of runs.

I know that intuition is not as good as a proof, yet it is a good starting point. If you plot in \$x,y\$ - plane points \$(i, a_i)\$, and then "draw" the curve through them, the intuition seems to be that the "smoother" the curve, the higher is performance of my implementation.

net.coderodde.util.sorting.CountingSort.java:

`package net.coderodde.util.sorting;

/**
* This clas

-
The sheer size and repetitive nature of Insertionsort.sort suggests splitting it up into methods, such as:

find_forward()
find_backward()
insert_before()
insert_after()

-
I don't see any benefit of starting a search form a last node. Always searching from the head gives the same asymptotic complexity (and assuming uniform inputs, the same worst case), and simplifies the logic.

StackExchange Code Review Q#100954, answer score: 3