Simple benchmarks comparing add+sort (timsort since Java 7) vs binary search+add for insertion into a sorted list

Benchmark.java

package timsort.minibench;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Random;

/**
 * <p>
 * Quick benchmark comparing two options for inserting an element into a sorted
 * list:
 * </p>
 *
 * <ul>
 * <li>add + Collections.sort (timsort, which has good performance for
 * near-sorted collections)</li>
 * <li>binary search + insertion</li>
 * </ul>
 *
 * <p>
 * I was wondering about timsort the other day when I ran into some code for
 * that from a student. This benchmark allows for easily adjusting the list size
 * and how much time we want to spend on the experiment by changing the
 * {@list #LIST_SIZE} and {@list #EXPERIMENT_MILLIS} constants.
 * <p>
 *
 * <p>
 * For lists of 100k elements and spending 100s per option, these are the
 * results:
 * </p>
 * 
 * <pre>
List size is 100000, experiment time is 100000 ms
Average time of 216061 sorted addition(s) with timsort.minibench.Benchmark$TimsortInserter: 0.462832 ms
Average time of 351384 sorted addition(s) with timsort.minibench.Benchmark$BinarySearchInserter: 0.284589 ms
 * </pre>
 *
 * <p>
 * No surprises here, but it is true that timsort doesn't do that bad at all!
 * </p>
 */
public class Benchmark {

	private static final int LIST_SIZE = 100_000;
	private static final int EXPERIMENT_MILLIS = 100 * 1000;

	private interface SortedInserter {
		void sortedAdd(List<Integer> l, int newValue);
	}

	private static class TimsortInserter implements SortedInserter {
		@Override
		public void sortedAdd(List<Integer> l, int newValue) {
			l.add(newValue);
			Collections.sort(l);
		}
	}

	private static class BinarySearchInserter implements SortedInserter {
		private int findSortedInsertionPoint(final int newEntry, List<Integer> copy) {
			int low = 0, high = copy.size();
			while (low < high) {
				final int midPosition = (low + high) / 2;
				final int midValue = copy.get(midPosition);

				if (midPosition == low) {
					// Interval (low, high) only covers two consecutive
					// positions
					if (newEntry <= midValue) {
						return low;
					} else {
						return high;
					}
				} else if (newEntry < midValue) {
					high = midPosition;
				} else if (newEntry > midValue) {
					low = midPosition;
				} else {
					return midPosition;
				}
			}
			return low;
		}

		@Override
		public void sortedAdd(List<Integer> l, int newValue) {
			int insertPosition = findSortedInsertionPoint(newValue, l);
			l.add(insertPosition, newValue);
		}
	}

	public static void main(String[] args) {
		final Random rnd = new Random();
		final List<Integer> original = new ArrayList<>(LIST_SIZE);
		for (int i = 0; i < LIST_SIZE; i++) {
			original.add(rnd.nextInt());
		}
		Collections.sort(original);
		System.out.println(String.format("List size is %d, experiment time is %d ms", LIST_SIZE, EXPERIMENT_MILLIS));

		final int commonSeed = rnd.nextInt();
		run(new Random(commonSeed), original, new TimsortInserter());
		run(new Random(commonSeed), original, new BinarySearchInserter());
	}

	protected static void run(final Random rnd, final List<Integer> original, final SortedInserter inserter) {
		final long startMillis = System.currentTimeMillis();
		long nDone = 0;
		while (System.currentTimeMillis() - startMillis < EXPERIMENT_MILLIS) {
			final int newEntry = rnd.nextInt();
			List<Integer> copy = new ArrayList<>(original);
			inserter.sortedAdd(copy, newEntry);

			if (!isSorted(copy)) {
				throw new IllegalStateException(String.format("List %s not sorted after adding %d", copy, newEntry));
			}
			++nDone;
		}
		final long endMillis = System.currentTimeMillis();
		double avg = (endMillis - startMillis) / (double) nDone;
		System.out.println(String.format("Average time of %d sorted addition(s) with %s: %f ms", nDone,
				inserter.getClass().getName(), avg));
	}

	private static boolean isSorted(List<Integer> l) {
		Iterator<Integer> it = l.iterator();

		int prev = it.next();
		while (it.hasNext()) {
			final int curr = it.next();
			if (curr < prev) {
				return false;
			}
			prev = curr;
		}
		return true;
	}

}