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 class implements an adaptive counting sort that adapts to the input.
*
* @author Rodion "rodde" Efremov
* @version 1.6
*/
public class CountingSort {

/**
* 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;
}

int lastElement = array[fromIndex];

for (int i = fromIndex + 1; i < toIndex; ++i) {
int currentElement = array[i];

if (currentElement < lastElement) {
Node tmp = last.prev;

while (tmp != null && tmp.element > currentElement) {
tmp = tmp.prev;
}

if (tmp == null) {
Node newnode = new Node(currentElement);
} else if (tmp.element == currentElement) {
tmp.count++;
last = 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;
last = newnode;
}
} else if (currentElement > lastElement) {
Node tmp = last.next;

while (tmp != null && tmp.element < currentElement) {
tmp = tmp.next;
}

if (tmp == null) {
Node newnode = new Node(currentElement);
newnode.prev = tail;
tail.next = newnode;
tail = newnode;
last = newnode;
} else if (tmp.element == currentElement) {
tmp.count++;
last = 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;
last = newnode;
}
} else {
last.count++;
}

lastElement = currentElement;
}

// Now rebuild the requested range.
int index = fromIndex;

for (Node node = head; node != null; node = node.next) {
int element = node.element;

for (int i = 0; i < node.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;
}
}


net.coderodde.util.sorting.Insertionsort.java:

package net.coderodde.util.sorting;

/**
* This class provides a static method for sorting integer arrays using
* insertion sort.
*
* @author Rodion "rodde" Efremov
* @version 1.6
*/
public class Insertionsort {

/**
* 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) {
for (int i = fromIndex + 1; i < toIndex; ++i) {
int element = array[i];
int j = i;

for (; j > fromIndex && array[j - 1] > element; --j) {
array[j] = array[j - 1];
}

array[j] = element;
}
}
}


Demo.java:

import java.util.Arrays;
import java.util.Random;
import java.util.stream.IntStream;
import net.coderodde.util.sorting.CountingSort;
import net.coderodde.util.sorting.Insertionsort;

public class Demo {

/**
* The number of iterations for each array type.
*/
private static final int OPERATION_COUNT = 30;

/**
* The maximum length of the array to profile against.
*/
private static final int LENGTH = 40000;

/**
* The assumed console window width in characters.
*/
private static final int CONSOLE_WIDTH = 80;

public static void main(final String... args) {
long seed = System.currentTimeMillis();
Random random = new Random(seed);

int[] array1;
int[] array2;

long totalMySort = 0L;
long totalInsertionsort = 0L;

System.out.println("Seed: " + seed);
System.out.println(title("Random arrays"));

//// RANDOM ARRAYS ////
for (int op = 0; op < OPERATION_COUNT; ++op) {
int maxValue = 20 + 20 * op;
System.out.println("Max value: " + maxValue);

array1 = getRandomIntegerArray(LENGTH, maxValue, random);
array2 = array1.clone();

int fromIndex = random.nextInt(LENGTH / 20);
int toIndex = LENGTH - random.nextInt(LENGTH / 20);

long startTime = System.currentTimeMillis();
CountingSort.sort(array1, fromIndex, toIndex);
long endTime = System.currentTimeMillis();
long duration = endTime - startTime;

System.out.println("Counting sort in " + duration
+ " milliseconds.");

totalMySort += duration;

startTime = System.currentTimeMillis();
Insertionsort.sort(array2, fromIndex, toIndex);
endTime = System.currentTimeMillis();
duration = endTime - startTime;

System.out.println("Insertion sort in " + duration
+ " milliseconds.");
System.out.println(bar());
totalInsertionsort += duration;

if (!Arrays.equals(array1, array2)) {
throw new RuntimeException("Sorts did not agree.");
}
}

System.out.println();
System.out.println(title("Presorted arrays"));

//// PRESORTED ARRAYS ////
for (int op = 0; op < OPERATION_COUNT; ++op) {
int runAmount = 20 + 20 * op;
System.out.println("Run amount: " + runAmount);

array1 = getPresortedIntegerArray(LENGTH, runAmount, random);
array2 = array1.clone();

int fromIndex = random.nextInt(LENGTH / 20);
int toIndex = LENGTH - random.nextInt(LENGTH / 20);

long startTime = System.currentTimeMillis();
CountingSort.sort(array1, fromIndex, toIndex);
long endTime = System.currentTimeMillis();
long duration = endTime - startTime;

System.out.println("Counting sort in " + duration
+ " milliseconds.");

totalMySort += duration;

startTime = System.currentTimeMillis();
Insertionsort.sort(array2, fromIndex, toIndex);
endTime = System.currentTimeMillis();
duration = endTime - startTime;

System.out.println("Insertion sort in " + duration
+ " milliseconds.");
System.out.println(bar());
totalInsertionsort += duration;

if (!Arrays.equals(array1, array2)) {
throw new RuntimeException("Sorts did not agree.");
}
}

System.out.println("Total insertion sort time: " +
totalInsertionsort + " milliseconds.");
System.out.println("Total counting sort time:  " +
totalMySort + " milliseconds.");
}

private static int[] getRandomIntegerArray(int size,
int maxValue,
Random random) {
return IntStream.range(0, size)
.map((i) -> random.nextInt(maxValue))
.toArray();
}

private static int[] getPresortedIntegerArray(int size,
int runs,
Random random) {
int[] ret = getRandomIntegerArray(size, size, random);
int chunkSize = size / runs + 1;
int chunkId = 0;

for (; chunkId < size / chunkSize; chunkId++) {
Arrays.sort(ret,
chunkSize * chunkId,
Math.min(size, (chunkId + 1) * chunkSize));
}

return ret;
}

private static String title(String s) {
int textWithSpacesLength = s.length() + 2;
int leftBarLength = (CONSOLE_WIDTH - textWithSpacesLength) / 2;
int rightBarLength = CONSOLE_WIDTH - leftBarLength
- textWithSpacesLength;

StringBuilder sb = new StringBuilder(CONSOLE_WIDTH);

for (int i = 0; i < leftBarLength; ++i) {
sb.append('-');
}

sb.append(' ').append(s).append(' ');

for (int i = 0; i < rightBarLength; ++i) {
sb.append('-');
}

return sb.toString();
}

private static String bar() {
StringBuilder sb = new StringBuilder(CONSOLE_WIDTH);

for (int i = 0; i < CONSOLE_WIDTH; ++i) {
sb.append('-');
}

return sb.toString();
}
}


My questions are:

1. How should I refactor the implementation in order to increase its maintainability/readability?
2. Is there any room for optimization?
3. What do you think of this algorithm?
• I'm not sure why you would ever use this over a radix sort. The radix sort uses the same sort of principles, except it is able to restrict the range to a certain number of bits (usually 8 bits or 256 buckets).
– JS1
Aug 14, 2015 at 18:27
• I have to disagree here: suppose you pass an array containing the same integer to radix sort. Assuming 8 bits, it will iterate through the entire range 4 times. Couting sort would be done in one pass. Aug 14, 2015 at 18:30
• On the other hand, if there are no duplicates, this sort is essentially an insertion sort, isn't it?
– JS1
Aug 14, 2015 at 19:24
• Yes, it would seem so. Aug 14, 2015 at 19:35

• 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.

The good part about this counting sort is the handling of duplicate entries: you just increment a count. The bad part is searching through a list to find the current entry. You could do better by using a TreeMap instead of a linked list, to reduce your linear search time to logarithmic. I believe this makes the total sort time $O(n \log n)$.

I think the code looks simpler also:

public static void sort(int[] array, int fromIndex, int toIndex) {
TreeMap<Integer,Integer> treeMap = new TreeMap<Integer,Integer>();

// Add all array entries into the tree map.
for (int i = fromIndex; i < toIndex; i++) {
int     key   = array[i];
Integer count = treeMap.get(key);
if (count != null) {
treeMap.put(key, count+1);
} else {
treeMap.put(key, 1);
}
}

// Pull out the entries from the tree map in order.
int index = fromIndex;
while (true) {
Map.Entry<Integer, Integer> entry = treeMap.pollFirstEntry();

if (entry == null) {
break;
}
int key   = entry.getKey();
int count = entry.getValue();
for (int i = 0; i < count; i++) {
array[index++] = key;
}
}
}


Output results

The sort runs faster also:

Total insertion sort time: 12003 milliseconds.
Total counting sort time:  477 milliseconds.

• No. Even better. I believe this is $\mathcal{O}(n \log k)$. Aug 15, 2015 at 9:09
• ..., where $k$ is the number of distinct keys, not $\max a_i - \min a_i$. Aug 16, 2015 at 16:15