I have refactored this. Once again, the running time can be anything between \$\Omega(n)\$ and \$\mathcal{O}(n^2)\$, yet it adapts to "smoothness" of the input array.
AdaptiveCountingSort.java:
package net.coderodde.util.sorting;
/**
* This class implements an adaptive counting sort that adapts to the input.
*
* @author Rodion "rodde" Efremov
* @version 1.6
*/
public class AdaptiveCountingSort {
/**
* Sorts the entire input integer array.
*
* @param array the integer array to sort.
*/
public static void sort(int[] array) {
sort(array, 0, array.length);
}
/**
* Sorts the range {@code array[fromIndex], array[fromIndex + 1], ...,
* array[toIndex - 2], array[toIndex - 1]}.
*
* @param array the array containing the range to sort.
* @param fromIndex the starting, inclusive range index.
* @param toIndex the ending, exclusive range index.
*/
public static void sort(int[] array, int fromIndex, int toIndex) {
if (toIndex - fromIndex < 2) {
return;
}
AdaptiveCountingSort sort = new AdaptiveCountingSort(array,
fromIndex,
toIndex);
sort.count();
sort.buildRange();
}
/**
* The node containing the least integer so far.
*/
private Node head;
/**
* The node containing the largest integer so far.
*/
private Node tail;
/**
* The node updated or created at previous array component.
*/
private Node previous;
/**
* The actual array containing the range to sort.
*/
private final int[] array;
/**
* The starting, inclusive index of the range to sort.
*/
private final int fromIndex;
/**
* The ending, exclusive index of the range to sort.
*/
private final int toIndex;
/**
* This field caches the previous array component.
*/
private int previousElement;
/**
* Constructs the state needed for sorting.
*
* @param array the array containing the range to sort.
* @param fromIndex the starting index of the range to sort.
* @param toIndex the ending index of the range to sort.
*/
private AdaptiveCountingSort(int[] array, int fromIndex, int toIndex) {
this.previousElement = array[fromIndex];
this.array = array;
this.fromIndex = fromIndex;
this.toIndex = toIndex;
this.head = this.tail = this.previous = new Node(previousElement);
}
// Handles 'currentElement' by inserting it in the proper location.
private void findAndUpdateSmallerNode(int currentElement) {
Node tmp = previous.prev;
// Go down the node chain towards the nodes with smaller keys.
while (tmp != null && tmp.element > currentElement) {
tmp = tmp.prev;
}
if (tmp == null) {
// 'currentElement' is the new minimum. Create new head node and put
// the integer in it.
Node newnode = new Node(currentElement);
newnode.next = head;
head.prev = newnode;
head = newnode;
previous = newnode;
} else if (tmp.element == currentElement) {
// The node containing 'currentElement' exists. Just increment the
// counter.
tmp.count++;
previous = tmp;
} else {
// Insert a new node between 'tmp' and 'tmp.next'.
Node newnode = new Node(currentElement);
newnode.prev = tmp;
newnode.next = tmp.next;
newnode.prev.next = newnode;
newnode.next.prev = newnode;
previous = newnode;
}
}
private void findAndUpdateLargerNode(int currentElement) {
Node tmp = previous.next;
// Go up the chain towards the nodes with larger keys.
while (tmp != null && tmp.element < currentElement) {
tmp = tmp.next;
}
// 'currentElement' is the new maximum. Create new tail node and put the
// integer in it.
if (tmp == null) {
Node newnode = new Node(currentElement);
newnode.prev = tail;
tail.next = newnode;
tail = newnode;
previous = newnode;
} else if (tmp.element == currentElement) {
// The node containing 'currentElement' exists. Just increment the
// counter.
tmp.count++;
previous = tmp;
} else {
// Insert a new node between 'tmp.prev' and 'tmp'.
Node newnode = new Node(currentElement);
newnode.prev = tmp.prev;
newnode.next = tmp;
tmp.prev.next = newnode;
tmp.prev = newnode;
previous = newnode;
}
}
// Constructs a sorted counter chain.
private void count() {
for (int i = fromIndex + 1; i < toIndex; ++i) {
int currentElement = array[i];
if (currentElement < previousElement) {
findAndUpdateSmallerNode(currentElement);
} else if (currentElement > previousElement) {
findAndUpdateLargerNode(currentElement);
} else {
previous.count++;
}
previousElement = currentElement;
}
}
// Reconstructs the node chain by dumping its content into input range.
private void buildRange() {
int index = fromIndex;
for (Node node = head; node != null; node = node.next) {
int element = node.element;
int count = node.count;
for (int i = 0; i < count; ++i) {
array[index++] = element;
}
}
}
private static final class Node {
Node(int element) {
this.element = element;
this.count = 1;
}
Node prev;
Node next;
int element;
int count;
}
}
Demo.java:
import java.util.Arrays;
import net.coderodde.util.sorting.AdaptiveCountingSort;
public class Demo {
private static final int LENGTH = 10_000_000;
public static void main(final String... args) {
testSin();
}
private static void testSin() {
System.out.println("testSin():");
int[] array1 = new int[LENGTH];
for (int i = 0; i < array1.length; ++i) {
array1[i] = (int)(20_000 * Math.sin(1.0 * i / 100_000));
}
int[] array2 = array1.clone();
long startTime = System.currentTimeMillis();
AdaptiveCountingSort.sort(array1, 10, array1.length - 10);
long endTime = System.currentTimeMillis();
System.out.println("Adaptive counting sort in " + (endTime - startTime) +
" milliseconds.");
startTime = System.currentTimeMillis();
Arrays.sort(array2, 10, array2.length - 10);
endTime = System.currentTimeMillis();
System.out.println("Arrays.sort in " + (endTime - startTime) +
" milliseconds.");
System.out.println("Equal: " + Arrays.equals(array1, array2));
}
}
The performance figures may be as optimistic as this:
testSin(): Adaptive counting sort in 76 milliseconds. Arrays.sort in 633 milliseconds. Equal: true
Please, tell me anything that comes to mind.
