Ordinary insertion sort vs. straight insertion sort in Java (benchmark)

Question

Intro

So this time I wanted to find out which of the two insertion sort flavours are faster:

Code

io.github.coderodde.util.StraightInsertionSort.java:

package io.github.coderodde.util;

/**
 * This class provides static methods for sorting integer arrays via insertion
 * sort and so called <b>straight</b> insertion sort.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.0.0 (Sep 18, 2025)
 * @since 1.0.0 (Sep 18, 2025)
 */
public final class StraightInsertionSort {

    private StraightInsertionSort() {
        
    }
    
    public static void insertionSort(int[] array) {
        for (int i = 1; i < array.length; ++i) {
            int j = i;
            
            while (j > 0 && array[j - 1] > array[j]) {
                swap(array, j - 1, j);
                --j;
            }
        }
    }
    
    public static void straightInsertionSort(int[] array) {
        for (int i = 1; i < array.length; ++i) {
            int x = array[i];
            int j = i;
            
            while (j > 0 && array[j - 1] > x) {
                array[j] = array[j - 1];
                --j;
            }
            
            array[j] = x;
        }
    }
    
    private static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
}

io.github.coderodde.util.bench.java:

package io.github.coderodde.util.benchmark;

import io.github.coderodde.util.StraightInsertionSort;
import java.util.Arrays;
import java.util.Random;

public final class Benchmark {
    
    private static final int LENGTH = 20_000;
    
    public static void main(String[] args) {
        int[] arr1 = getRandomArray(LENGTH, new Random());
        int[] arr2 = arr1.clone();
        
        long ta = System.currentTimeMillis();
        StraightInsertionSort.insertionSort(arr1);
        long tb = System.currentTimeMillis();
        
        System.out.println(
                "Ordinary insertion sort: " + (tb - ta) + " milliseconds.");
        
        ta = System.currentTimeMillis();
        StraightInsertionSort.straightInsertionSort(arr2);
        tb = System.currentTimeMillis();
        
        System.out.println(
                "Straight insertion sort: " + (tb - ta) + " milliseconds.");
    
        System.out.println("Algorithms agree: " + (Arrays.equals(arr1, arr2)));
    }
    
    private static int[] getRandomArray(int length, Random random) {
        int[] array = new int[length];
        
        for (int i = 0; i < array.length; ++i) {
            array[i] = random.nextInt();
        }
        
        return array;
    }
}

Typical output

I got this occasionally:

Ordinary insertion sort: 124 milliseconds.
Straight insertion sort: 61 milliseconds.
Algorithms agree: true

Critique request

Could you please review my benchmark runner?

I've never before known your "straight" variant to be distinguished with its own name, but FWIW, that's how I always write insertion sort. — John Bollinger
– John Bollinger, Commented Sep 18 at 21:57
See also this answer for an additional algorithmic optimization that can be applied to insertion sort. It would be suitable for both of your variants. — John Bollinger
– John Bollinger, Commented Sep 18 at 22:00
You could consider testing other kinds of inputs than random, too. For example, I'd expect the two to perform about the same for approximately in-order inputs, whereas I would expect the "straight" variant to have even more of an advantage for reverse-sorted ones. — John Bollinger
– John Bollinger, Commented Sep 18 at 22:09

user555045 · Accepted Answer · 2025-09-18 13:00:22Z

Could you please review my benchmark runner?

Let's say that this is the style of benchmarking that you want to do, and not eg JMH. That will make some people angry and they'll insist that there is only One True Way to benchmark - not me though, with only a bit more care you can make it Good Enough (for the purpose of this test). Extreme accuracy isn't really required here.

But the benchmark could avoid a couple of pitfalls that it currently does not avoid.

currentTimeMillis is affected by System Time and therefore adjustments due to NTP syncing the time. I happened to actually catch that in the act (probably?), I saw one negative time which I otherwise cannot explain (I know of other reasons, but the effects of them are very small, on the order of dozens of nanoseconds, so they could not make this benchmark show a negative time), but that's going to be quite rare so I got super lucky (or unlucky) here. nanoTime at least doesn't have that issue, the "measure the distance to the moon to nanometer accuracy" benchmarking crowd will still call it unreliable but it'll do in this context.
Repeating the benchmark by relaunching the entire program does not eliminate startup delays, processor frequency changes, or the transition from c1 to c2 compilation, so the benchmark should loop a couple of times internally and the initial results should not be trusted (the initial iterations measure something, but probably not the thing you want to measure).

So I got this:

Ordinary insertion sort: 94 milliseconds.
Straight insertion sort: 30 milliseconds.
Ordinary insertion sort: 96 milliseconds.
Straight insertion sort: 28 milliseconds.
Ordinary insertion sort: 81 milliseconds.
Straight insertion sort: 15 milliseconds.
Ordinary insertion sort: 81 milliseconds.
Straight insertion sort: 17 milliseconds.
Ordinary insertion sort: 80 milliseconds.
Straight insertion sort: 19 milliseconds.
Ordinary insertion sort: 83 milliseconds.
Straight insertion sort: 18 milliseconds.
Ordinary insertion sort: 80 milliseconds.
Straight insertion sort: 15 milliseconds.
Ordinary insertion sort: 81 milliseconds.
Straight insertion sort: 16 milliseconds.
Ordinary insertion sort: 81 milliseconds.
Straight insertion sort: 17 milliseconds.
Ordinary insertion sort: 82 milliseconds.
Straight insertion sort: 16 milliseconds.

In order to do this, I of course had to make more copies of the array to avoid re-sorting a now sorted array, while not including the time it took to copy them (but that's not much). I used nanoTime but converted to milliseconds.

The times changed at some point (after the first couple of iterations) but more importantly the performance ratio also changed at that point, 94/30 and 81/16 are I think diffent enough to care about the difference, though neither of them leaves much doubt as to which approach is faster.

10 iterations is nowhere near enough to properly ‘warm up’ the JVM; tens of thousands are likely to be needed. See this question. (That's just one reason why people recommend using an existing benchmarking framework rather than trying to discover and work around all these effects yourself.) — gidds
– gidds, Commented Sep 19 at 8:41
@gidds that would take half an hour, I mean literally, do the math. This is not a microbenchmark, the code-under-test is not micro (that also means that we can conveniently disregard the difference between latency and throughput, which we normally cannot, but your linked question barely touches on - in small cases it requires not just careful timing but careful design of the dependency structure of the benchmark). — user555045
– user555045, Commented Sep 19 at 9:01
@gidds linked Q&A is not even sufficient for actual microbenchmarks. Severely under-highlights various effects that aren't due to java itself: CPU frequency changing, dependency structure, speculation barriers (how do you even do them in java, in assembly we'd use lfence these days, cpuid in the past), negating the overhead of the measurement (eg subtracting a "null measurement"). — user555045
– user555045, Commented Sep 19 at 9:28
It might be useful to future readers if you specify what CPU model and frequency, and JVM version you used for your benchmark results. You never know when someone's going to be looking for how an Ice Lake or Zen 3 or whatever performed on a certain type of microbenchmark, especially one with source they can try themselves. — Peter Cordes
– Peter Cordes, Commented Sep 20 at 4:22
Also related: Idiomatic way of performance evaluation? covers a lot of the (micro)-benchmarking gotchas. (I'd tend to call this a micro-benchmark because the amount of code involved is small, just one function so any special CPU-uarch quirks that affect that loop can have an outsized effect. But yes, the run-time is long enough that it doesn't need a repeat-loop to be usefully timed with simple methods.) — Peter Cordes
– Peter Cordes, Commented Sep 20 at 4:24

Chris · Accepted Answer · 2025-09-19 05:47:53Z

The simplest change would be to simply have a larger sample size than one run of each method and to compile all of the results into arraylists and then perform some level of statistical analysis on them. The simplest being just displaying averages. If you want to be more complex you can start calculating standard deviations and make sure your data makes sense.

    public static void main(String[] args) {
        ArrayList<Integer> straightRuntimes = ArrayList<>();
        ArrayList<Integer> ordinaryRuntimes = ArrayList<>();

        for (int i = 0; i < NUMBER_OF_REPS) {
            int[] arr1 = getRandomArray(LENGTH, new Random());
            int[] arr2 = arr1.clone();
        
            long ta = System.currentTimeMillis();
            StraightInsertionSort.insertionSort(arr1);
            long tb = System.currentTimeMillis();

            straightRuntimes.add(tb - ta);  
        
            ta = System.currentTimeMillis();
            StraightInsertionSort.straightInsertionSort(arr2);
            tb = System.currentTimeMillis();
        
            ordinaryRuntimes.add(tb - ta);
        }

        // Statistical report goes here
    }

Stack Exchange Network

Ordinary insertion sort vs. straight insertion sort in Java (benchmark)

Intro

Code

Typical output

Critique request

2 Answers 2

You must log in to answer this question.

Linked

Hot Network Questions

Ordinary insertion sort vs. straight insertion sort in Java (benchmark)

Intro

Code

Typical output

Critique request

2 Answers 2

You must log in to answer this question.

Linked

Related

Hot Network Questions