Comb sort in Java

Question

Comb sort may be thought of as a generalization of bubble sort. The following is my implementation:

package net.coderodde.util.sorting;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;
/**
 * This class implements 
 * <a href="https://en.wikipedia.org/wiki/Comb_sort">Comb sort</a>.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Nov 29, 2015)
 */
public class CombSort {
 private static final float SHRINK_FACTOR = 1.3f;
 public static <T> void sort(T[] array,
 int fromIndex, 
 int toIndex,
 Comparator<? super T> comparator) {
 int rangeLength = toIndex - fromIndex;
 if (rangeLength < 2) {
 return;
 }
 int gap = rangeLength;
 boolean swapped = true;
 while (gap >= 1 && swapped) {
 gap = Math.max(1, (int)(gap / SHRINK_FACTOR));
 swapped = false;
 for (int i = fromIndex; i + gap < toIndex; ++i) {
 if (comparator.compare(array[i], array[i + gap]) > 0) {
 T tmp = array[i];
 array[i] = array[i + gap];
 array[i + gap] = tmp;
 swapped = true;
 }
 }
 }
 }
 public static <T> void sort(T[] array, Comparator<? super T> comparator) {
 sort(array, 0, array.length, comparator);
 }
 private static final int ARRAY_LENGTH = 1_000_000;
 private static final int FROM_INDEX = 100;
 private static final int TO_INDEX = ARRAY_LENGTH - 100;
 public static void main(final String... args) {
 long seed = System.nanoTime();
 Random random = new Random(seed);
 Integer[] array1 = createRandomIntegerArray(ARRAY_LENGTH, random);
 Integer[] array2 = array1.clone();
 System.out.println("Seed = " + seed);
 long startTime = System.nanoTime();
 CombSort.sort(array1, FROM_INDEX, TO_INDEX, Integer::compare);
 long endTime = System.nanoTime();
 System.out.printf("Comb sort in %.2f milliseconds.\n",
 1.0 * (endTime - startTime) / 1e6);
 startTime = System.nanoTime();
 Arrays.sort(array2, FROM_INDEX, TO_INDEX, Integer::compare);
 endTime = System.nanoTime();
 System.out.printf("Arrays.sort in %.2f milliseconds.\n",
 1.0 * (endTime - startTime) / 1e6);
 System.out.println("Arrays identical: " + 
 equalByReference(array1, array2));
 }
 private static <T> boolean equalByReference(T[] array1, T[] array2) {
 if (array1.length != array2.length) {
 return false;
 }
 for (int i = 0; i < array1.length; ++i) {
 if (array1[i] != array2[i]) {
 return false;
 }
 }
 return true;
 }
 private static Integer[] createRandomIntegerArray(int size, Random random) {
 Integer[] array = new Integer[size];
 for (int i = 0; i < size; ++i) {
 array[i] = random.nextInt(100);
 }
 return array;
 }
}

When comparing to Arrays.sort on random integer arrays of size one million components, I get the following figures:

Seed = 602726627320375
Comb sort in 499.82 milliseconds.
Arrays.sort in 948.06 milliseconds.
Arrays identical: true

Anything to improve there?

Answer 1

I made an argument validation to the method. Changed the while loop to do_while loop. Swapped the condition check order in the do_while loop (I think it should be more efficient and a bit more readable that way).

public static <T> void sort(T[] array,
 int fromIndex, 
 int toIndex,
 Comparator<? super T> comparator) {
 if (fromIndex >= toIndex) {
 throw new IllegalArgumentException("fromIndex must be lower than toIndex");
 }
 int elementsToSort = toIndex - fromIndex;
 if (elementsToSort > 1) {
 sortImpl(array, fromIndex, toIndex, comparator);
 }
}
private static <T> void sortImpl(T[] array,
 int fromIndex, 
 int toIndex,
 Comparator<? super T> comparator) {
 int gap = toIndex - fromIndex;
 boolean swapped;
 do {
 gap = Math.max(1, (int)(gap / SHRINK_FACTOR));
 swapped = false;
 for (int i = fromIndex; i + gap < toIndex; ++i) {
 if (comparator.compare(array[i], array[i + gap]) > 0) {
 T tmp = array[i];
 array[i] = array[i + gap];
 array[i + gap] = tmp;
 swapped = true;
 }
 }
 } while (swapped && gap >= 1);
}

Note: Consider adding a sort method that would not operate on the instance of the array:

public static <T> T[] sorted(T[] array,
 int fromIndex, 
 int toIndex,
 Comparator<? super T> comparator) {
 if (fromIndex >= toIndex) {
 throw new IllegalArgumentException("fromIndex must be lower than toIndex");
 }
 T[] result = array.clone();
 sort(result, fromIndex, toIndex, comparator);
 return result;
}
public static <T> T[] sorted(T[] array, Comparator<? super T> comparator) {
 return sorted(array, 0, array.length, comparator);
}