Return to Question

(See the next iteration.)

(See the next iteration.)

(See the next iteration .)

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

My code follows:

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];
 Node head = new Node(lastElement);
 Node tail = head;
 Node last = head;
 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);
 newnode.next = head;
 head.prev = newnode;
 head = newnode;
 last = head;
 } 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;
 }
}

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

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();
 }
}

1. How should I refactor the implementation in order to increase its maintainability/readability?
2. Is there any room for optimization?
3. Have you seen that algorithm anywhere? If not, what do you think about it?

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

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];
 Node head = new Node(lastElement);
 Node tail = head;
 Node last = head;
 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);
 newnode.next = head;
 head.prev = newnode;
 head = newnode;
 last = head;
 } 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;
 }
}

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

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();
 }
}

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?