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