Comparing binary insertion sort with straight insertion sort in Java

Question

Straight insertion sort

When inserting an element into its proper location to the left, one can achieve that by \$n\$ adjacent swaps which totals to \$3n\$ assignments. Straight insertion sort, instead, stores the element and than performs \$n\$ chain shifts to the right.

Binary insertion sort

Just like conventional insertion sort, but the search for the insertion point is done via binary search, reducing the worst-case running time for pivot search from \$\Theta(n)\$ to \$\Theta(\log n)\$.

Code

com.github.coderodde.util.BinaryInsertionSort.java:

package com.github.coderodde.util;

import java.util.Comparator;

/**
 * This class implements binary insertion sort, which, unlike conventional 
 * insertion sort, relies on binary search when searching the position to insert
 * the pivot element into.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (May 12, 2020) ~ initial version.
 * @since 1.6 (May 12, 20202)
 */
public final class BinaryInsertionSort {

    private BinaryInsertionSort() {}

    /**
     * Sorts the input range {@code array[fromIndex], ..., array[toIndex - 1]}
     * into ascending order.
     * 
     * @param <E> the array component type.
     * @param array the array holding the target range.
     * @param fromIndex the first inclusive range index.
     * @param toIndex the last exclusive range index.
     * @param comparaotr the comparator object.
     */
    public static <E> void sort(E[] array,
                                int fromIndex,
                                int toIndex,
                                Comparator<? super E> comparaotr) {

        for (int currentIndex = fromIndex + 1; 
                currentIndex < toIndex;
                currentIndex++) {
            final E pivot = array[currentIndex];

            int left = fromIndex;
            int right = currentIndex;

            while (left < right) {
                final int middle = (left + right) >>> 1;

                if (comparaotr.compare(pivot, array[middle]) < 0) {
                    right = middle;
                } else {
                    left = middle + 1;
                }
            }

            assert left == right;

            final int n = currentIndex - left;

            switch (n) {
                case 2: array[left + 2] = array[left + 1];
                case 1: array[left + 1] = array[left];
                    break;

                default:
                    System.arraycopy(array, left, array, left + 1, n);
            }
        }
    }

    /**
     * Sorts the input array range into ascending order using a natural 
     * comparator.
     * 
     * @param <E> the array component type.
     * @param array the array holding the target range.
     * @param fromIndex the first inclusive range index.
     * @param toIndex the last exclusive range index.
     */
    public static <E> void sort(E[] array, int fromIndex, int toIndex) {
        sort(array, fromIndex, toIndex, new Comparator<E>() {
            @Override
            public int compare(final E elementLeft, final E elementRight) {
                return ((Comparable<E>) elementLeft).compareTo(elementRight);
            }
        });
    }

    /**
     * Sorts the entire input array into ascending order.
     * 
     * @param <E> the array component type.
     * @param array the target array to sort.
     */
    public static <E> void sort(E[] array) {
        sort(array, 0, array.length);
    }

    /**
     * Sorts the entire input array using the specifying comparator.
     * 
     * @param <E> the array component type.
     * @param array the target array to sort.
     * @param comparator the comparator object.
     */
    public static <E> void sort(E[] array, Comparator<? super E> comparator) {
        sort(array, 0, array.length, comparator);
    }
}

com.github.coderodde.util.StraightInsertionSort.java:

package com.github.coderodde.util;

import java.util.Comparator;


/**
 * This class implements straight insertion sort, which differs from ordinary 
 * insertion sort by the fact that it does not shift the subranges to shift by
 * swapping the element, but instead by saving the rightmost element, shifting
 * everything in the shift range one position to the right and inserting the
 * saved element into its correct position.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (May 11, 2020) ~ initial version.
 * @see 1.6 (May 11, 2020)
 */
public final class StaightInsertionSort {

    private StaightInsertionSort() {}

    /**
     * Sorts the input array range into ascending order using an explicit 
     * comparator.
     * 
     * @param <E> the array component type.
     * @param array the array holding the target range.
     * @param fromIndex the first inclusive range index.
     * @param toIndex the last exclusive range index.
     * @param comparator the comparator.
     */
    public static <E> void sort(E[] array, 
                                int fromIndex,
                                int toIndex,
                                Comparator<? super E> comparator) {

        for (int i = fromIndex + 1; i < toIndex; i++) {
            final E targetElement = array[i];
            int j = i - 1;

            while (j >= fromIndex 
                    && comparator.compare(array[j], targetElement) > 0) {
                array[j + 1] = array[j];
                j--;
            }

            array[j + 1] = targetElement;
        }
    }

    /**
     * Sorts the input array range into ascending order using a natural 
     * comparator.
     * 
     * @param <E> the array component type.
     * @param array the array holding the target range.
     * @param fromIndex the first inclusive range index.
     * @param toIndex the last exclusive range index.
     */
    public static <E> void sort(E[] array, int fromIndex, int toIndex) {
        sort(array, fromIndex, toIndex, new Comparator<E>() {
            @Override
            public int compare(final E elementLeft, final E elementRight) {
                return ((Comparable<E>) elementLeft).compareTo(elementRight);
            }
        });
    }

    public static <E> void sort(E[] array) {
        sort(array, 0, array.length);
    }

    public static <E> void sort(E[] array, Comparator<? super E> comparator) {
        sort(array, 0, array.length, comparator);
    }
}

com.github.coderodde.util.BinaryInsertionSortTest.java:

package com.github.coderodde.util;

import static com.github.coderodde.util.SharedSortingTestUtils.getRandomIntegerArray;
import java.util.Arrays;
import java.util.Random;
import org.junit.Test;
import static org.junit.Assert.*;

/**
 * This unit test class tests the binary insertion sort algorithm 
 * ({@link com.github.coderodde.util.BinaryInsertionSort}).
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (May 12, 2020) ~ initial version.
 * @since 1.6 (May 12, 2020)
 */
public class BinaryInsertionSortTest {
    public static final int REPETITIONS = 10_000;
    public static final int LENGTH = 100;

    @Test
    public void bruteForceTest() {
        long seed = System.currentTimeMillis();
        System.out.println("Seed = " + seed);
        Random random = new Random();

        for (int repetition = 0; repetition < REPETITIONS; repetition++) {
            Integer[] array1 = getRandomIntegerArray(random, LENGTH);
            Integer[] array2 = array1.clone();

            int index1 = random.nextInt(LENGTH), 
                index2 = random.nextInt(LENGTH);

            int fromIndex = Math.min(index1, index2);
            int toIndex   = Math.max(index1, index2);

            Arrays.sort(array1, fromIndex, toIndex);
            StaightInsertionSort.sort(array2, fromIndex, toIndex);

            assertTrue(Arrays.equals(array1, array2));
        }
    }
}

com.github.coderodde.util.StraightInsertionSortTest.java:

package com.github.coderodde.util;

import static com.github.coderodde.util.SharedSortingTestUtils.getRandomIntegerArray;
import java.util.Arrays;
import java.util.Random;
import static org.junit.Assert.assertTrue;
import org.junit.Test;

/**
 * This unit test class tests the binary insertion sort algorithm 
 * ({@link com.github.coderodde.util.StaightInsertionSort}).
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (May 12, 2020) ~ initial version.
 * @since 1.6 (May 12, 2020)
 */
public class StaightInsertionSortTest {

    public static final int REPETITIONS = 10_000;
    public static final int LENGTH = 100;

    @Test
    public void bruteForceTest() {
        long seed = System.currentTimeMillis();
        System.out.println("Seed = " + seed);
        Random random = new Random();

        for (int repetition = 0; repetition < REPETITIONS; repetition++) {
            Integer[] array1 = getRandomIntegerArray(random, LENGTH);
            Integer[] array2 = array1.clone();

            int index1 = random.nextInt(LENGTH), 
                index2 = random.nextInt(LENGTH);

            int fromIndex = Math.min(index1, index2);
            int toIndex   = Math.max(index1, index2);

            Arrays.sort(array1, fromIndex, toIndex);
            StaightInsertionSort.sort(array2, fromIndex, toIndex);

            assertTrue(Arrays.equals(array1, array2));
        }
    }
}

com.github.coderodde.util.SharedSortingTestUtils.java:

package com.github.coderodde.util;

import java.util.Random;

/**
 * This class provides shared facilities for unit testing.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (May 12, 2020) ~ initial version.
 * @since 1.6 (May 12, 2020)
 */
class SharedSortingTestUtils {

    static Integer[] getRandomIntegerArray(Random random, int length) {
        Integer[] array = new Integer[length];

        for (int i = 0; i < length; i++) {
            array[i] = random.nextInt();
        }

        return array;
    }   
}

com.github.coderodde.util.Demo.java

package com.github.coderodde.util;

import java.util.Random;

/**
 * This class implements a demonstration comparing performance of straight 
 * and binary insertion sort algorithms.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (May 12, 2020) ~ initial version.
 * @since 1.6 (May 12, 2020)
 */
public class Demo {

    public static final int REPETITIONS = 100_000;
    public static final int MAX_LENGTH_NORMAL = 2048;
    public static final int MAX_LENGTH_SMALL = 64;

    interface SortingAlgorithm<E> {
        public void sort(E[] array,
                         int fromIndex, 
                         int toIndex);
    }

    public static void main(String[] args) {
        long seed = System.currentTimeMillis();
        System.out.println("seed = " + seed);
        Random random = new Random(seed);

        ///////////////////////////////////////////
        System.out.println("--- Small arrays ---");
        warmupSmall(random, seed);
        benchmarkSmall(random, seed);
        ////////////////////////////////////////////
        System.out.println("--- Normal arrays ---");
        warmupNormal(random, seed);
        benchmarkNormal(random, seed);
    }

    static void warmupSmall(Random random, long seed) {
        random.setSeed(seed);
        System.out.print("Warmed up ");
        System.out.print(StaightInsertionSort.class.getSimpleName());

        warmup(MAX_LENGTH_SMALL,
               REPETITIONS,
               random,
               StaightInsertionSort::sort);

        random.setSeed(seed);
        System.out.print("Warmed up ");
        System.out.print(BinaryInsertionSort.class.getSimpleName());

        warmup(MAX_LENGTH_SMALL,
               REPETITIONS,
               random,
               BinaryInsertionSort::sort);
    }

    static void benchmarkSmall(Random random, long seed) {
        random.setSeed(seed);
        System.out.print("Benchmarked ");
        System.out.print(StaightInsertionSort.class.getSimpleName());

        benchmark(MAX_LENGTH_SMALL,
                  REPETITIONS,
                  random,
                  StaightInsertionSort::sort);

        random.setSeed(seed);
        System.out.print("Benchmarked ");
        System.out.print(BinaryInsertionSort.class.getSimpleName());

        benchmark(MAX_LENGTH_SMALL,
                  REPETITIONS,
                  random,
                  BinaryInsertionSort::sort);
    }

    static void warmupNormal(Random random, long seed) {
        random.setSeed(seed);
        System.out.print("Warmed up ");
        System.out.print(StaightInsertionSort.class.getSimpleName());

        warmup(MAX_LENGTH_NORMAL,
               REPETITIONS,
               random,
               StaightInsertionSort::sort);

        random.setSeed(seed);
        System.out.print("Warmed up ");
        System.out.print(BinaryInsertionSort.class.getSimpleName());

        warmup(MAX_LENGTH_NORMAL,
               REPETITIONS,
               random,
               BinaryInsertionSort::sort);
    }

    static void benchmarkNormal(Random random, long seed) {
        random.setSeed(seed);
        System.out.print("Benchmarked ");
        System.out.print(StaightInsertionSort.class.getSimpleName());

        benchmark(MAX_LENGTH_NORMAL,
                  REPETITIONS,
                  random,
                  StaightInsertionSort::sort);

        random.setSeed(seed);
        System.out.print("Benchmarked ");
        System.out.print(BinaryInsertionSort.class.getSimpleName());

        benchmark(MAX_LENGTH_NORMAL,
                  REPETITIONS,
                  random,
                  BinaryInsertionSort::sort);
    }

    static void perform(boolean isBenchmark,
                        int maxLength, 
                        int repetitions, 
                        Random random,
                        SortingAlgorithm<Integer> sortingAlgorithm) {

        long startTime = System.currentTimeMillis();

        for (int repetition = 0; repetition < repetitions; repetition++) {
            Integer[] array = getRandomIntegerArray(random, maxLength);

            int index1 = random.nextInt(maxLength);
            int index2 = random.nextInt(maxLength);

            int fromIndex = Math.min(index1, index2);
            int toIndex   = Math.max(index1, index2);

            sortingAlgorithm.sort(array, 
                                  fromIndex, 
                                  toIndex);
        }   

        System.out.println(" in " + (System.currentTimeMillis() - startTime) + 
                           " milliseconds.");
    }

    static void benchmark(int length, 
                          int repetitions, 
                          Random random, 
                          SortingAlgorithm sortingAlgorithm) {
        perform(true, length, repetitions, random, sortingAlgorithm);
    }

    static void warmup(int length, 
                       int repetitions, 
                       Random random, 
                       SortingAlgorithm sortingAlgorithm) {
        perform(false, length, repetitions, random, sortingAlgorithm);
    }

    static Integer[] getRandomIntegerArray(Random random, int length) {
        Integer[] array = new Integer[length];

        for (int i = 0; i < length; i++) {
            array[i] = random.nextInt();
        }

        return array;
    }
}

(The GitHub repository for this project is here.)

Sample output

seed = 1589305635492
--- Small arrays ---
Warmed up StaightInsertionSort in 160 milliseconds.
Warmed up BinaryInsertionSort in 133 milliseconds.
Benchmarked StaightInsertionSort in 125 milliseconds.
Benchmarked BinaryInsertionSort in 129 milliseconds.
--- Normal arrays ---
Warmed up StaightInsertionSort in 30890 milliseconds.
Warmed up BinaryInsertionSort in 6897 milliseconds.
Benchmarked StaightInsertionSort in 32279 milliseconds.
Benchmarked BinaryInsertionSort in 7022 milliseconds.

Critique request

First and foremost, I would like to hear your opinions on unit testing. Does generating a bunch of input instances and comparing the sort output to Arrays.sort output a good idea? I tried also to deal with warming up the JVM, yet I did not use any funky third-party libraries for that.

Answer 1

The only reason BinaryInsertionSort outperforms StraightInsertionSort is that it is in the position to call System.arraycopy, which I expect to be highly optimized (possibly all the way down to memcpy), and much faster than the element-by-element copying loop StraightInsertionSort does. It tastes like cheating. You compare apples to oranges.

From the purely algorithmic point of view, both versions copy elements the same number of times. Binary version may do less comparisons. However, it may do way more. Consider the case of sorting a sorted array. Both versions do zero copies. Straight sort does 1 comparison per element; \$O(n)\$ total. Binary sort does \$\log k\$ comparisons per element; \$O(n\log n)\$ total.

Also, the straight sort implementation is suboptimal. It does two comparisons per inner loop iteration: j >= fromIndex and comparator.compare(array[j], targetElement) > 0. It is possible to get away with one:

        if (comparator.compare(array[fromIndex], targetElement > 0) {
            // The target element is less than all other elements. We
            // don't need to compare values anymore.
            // NB: May as well call System.arraycopy here.
            while (j >= fromIndex) {
                array[j+1] = array[j];
                j--;
        } else {
            // The leftmost element is now a natural sentinel. We don't
            // need to compare indices anymore.
            while (comparator.compare(array[j], targetElement) > 0) {
                array[j+1] = array[j];
                j--;
            }
        }

---

The only practical application of the insertion sort I am aware of is sorting almost sorted arrays, that is those in which every element is within fixed small distance k from its final position (e.g. quicksort with the recursion cutoff). Benchmarking such arrays will be most instructive. Try a 100 million-strong array with k = 16.

Answer 2

            while (j >= fromIndex 
                    && comparator.compare(array[j], targetElement) > 0) {
                array[j + 1] = array[j];
                j--;
            }

This code does two things. It finds the insertion point and it moves the existing elements. It could do just one thing.

            while (j >= fromIndex 
                    && comparator.compare(array[j], targetElement) > 0) {
                j--;
            }

Now it only finds the insertion point.

Then you can insert with something like

            final int n = i - j;

            switch (n) {
                case 2: array[j + 2] = array[j + 1];
                case 1: array[j + 1] = array[j];
                case 0:
                    break;

                default:
                    System.arraycopy(array, j, array, j + 1, n);
            }
            array[j] = targetElement;

Not tested for fencepost errors, etc. You may have to increment j before this. But this should show the essential concept.

Now both algorithms use essentially the same insertion code and you can compare the time to find the insertion point more directly. So if your goal is to compare the two methods of finding the insertion point, this would be a better test. It more clearly isolates that difference.

Another alternative would be to stop using System.arraycopy and write a manual move routine in your binary insertion sort. That would also fix the problem of comparability.

Answer 3

I would like to hear your opinions on unit testing

Way to go. When I saw BinaryInsertionSort.sort(E[] array, int fromIndex, int toIndex, Comparator<? super E> comparaotr), I was dubious it worked - after all, my spelling checker flagged the last parameter. Gave it a backhanded try:

    public static void main(String[] args) {
        Integer[]a = { 1, 3, 2, 0 };
        sort(a);
        System.out.println(java.util.Arrays.toString(a));
    }

[1, 1, 3, 3]

When I scrolled through the question, I rolled my eyes for the code duplicated among StraightInsertionSortTest.java and BinaryInsertionSortTest.java.
Further down, BinaryInsertionSortTest.bruteForceTest() reads

            StaightInsertionSort.sort(array2, fromIndex, toIndex);

Lesson: I need a better spelling checker. Marking all of StaightInsertionSort had me miss the typo in the first word.
(How on earth did you get that accepted in a StraightInsertionSortTest.java?!)