Benchmarking in Java some super linearithmic sorting algorithms

Intro

A sort is called super linearithmic if its running time is \$\omega(N \log N)\$. For example, \$f(N) = \omega(g(N))\$ means that \$f(N)\$ grows "faster" than \$g(N)\$. In this post, I will compare four (4) such algorithms against java.util.Arrays.sort:

• Insertion sort
• Bubble sort
• Comb sort
• Shellsort

Code

io.github.coderodde.util.Arrays.java:

package io.github.coderodde.util;

/**
 * This class contains some comparison sorts.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.0.0 (Oct 31, 2025)
 * @since 1.0.0 (Oct 31, 2025)
 */
public final class Arrays {

    private static final int[] SHELL_SORT_GAPS =
    { 701, 301, 132, 57, 23, 10, 4, 1 };
    
    private Arrays() {
        
    }
    
    public static <E extends Comparable<? super E>> 
        void insertionSort(E[] array) {
        for (int i = 1; i < array.length; ++i) {
            E x = array[i];
            int j = i;
            
            while (j > 0 && array[j - 1].compareTo(x) > 0) {
                array[j] = array[j - 1];
                --j;
            }
            
            array[j] = x;
        }
    }
        
    public static <E extends Comparable<? super E>> void bubbleSort(E[] array) {
        boolean swapped;
        int n = array.length;
        
        do {
            swapped = false;
            
            for (int i = 1; i < n; ++i) {
                if (array[i - 1].compareTo(array[i]) > 0) {
                    swap(array, i - 1, i);
                    swapped = true;
                }
            }
            
            --n;
        } while (swapped);
    }
    
    public static <E extends Comparable<? super E>> void combSort(E[] array) {
        int gap = array.length;
        float shrinkFactor = 1.3f;
        boolean sorted = false;
        
        while (!sorted) {
            gap = (int)(gap / shrinkFactor);
            
            if (gap <= 1) {
                gap = 1;
                sorted = true;
            } else if (gap == 9 || gap == 10) {
                gap = 11;
            }
            
            for (int i = 0; i + gap < array.length; ++i ){
                if (array[i].compareTo(array[i + gap]) > 0) {
                    swap(array, i, i + gap);
                    sorted = false;
                }
            }
        }
    }
    
    public static <E extends Comparable<? super E>> void shellSort(E[] array) {
        for (int gap : SHELL_SORT_GAPS) {
            for (int i = gap; i < array.length; ++i) {
                E tmp = array[i];
                int j = i;
                
                for (; 
                    (j >= gap) && (array[j - gap].compareTo(tmp) > 0); 
                     j -= gap) {
                 
                    array[j] = array[j - gap];
                }
                
                array[j] = tmp;
            }
        }
    }
    
    private static <E> void swap(E[] array, int i, int j) {
        E tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
}

io.github.coderodde.util.demo.Demo.java:

package io.github.coderodde.util.demo;

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

public final class Demo {

    private static final int ARRAY_LENGTH = 50_000;
    
    public static void main(String[] args) {
        Integer[] arr1 = getRandomArray();
        Integer[] arr2 = arr1.clone();
        Integer[] arr3 = arr1.clone();
        Integer[] arr4 = arr1.clone();
        Integer[] arr5 = arr1.clone();
        
        long ta = System.currentTimeMillis();
        Arrays.insertionSort(arr1);
        long tb = System.currentTimeMillis();
        
        System.out.println(
                "Insertion sort in: " + (tb - ta) + " milliseconds.");
        
        ta = System.currentTimeMillis();
        Arrays.bubbleSort(arr2);
        tb = System.currentTimeMillis();
        
        System.out.println(
                "Bubble sort in:    " + (tb - ta) + " milliseconds.");
        
        ta = System.currentTimeMillis();
        Arrays.combSort(arr3);
        tb = System.currentTimeMillis();
        
        System.out.println(
                "Comb sort in:      " + (tb - ta) + " milliseconds.");
        
        ta = System.currentTimeMillis();
        Arrays.combSort(arr4);
        tb = System.currentTimeMillis();
        
        System.out.println(
                "Shell sort in:     " + (tb - ta) + " milliseconds.");
        
        ta = System.currentTimeMillis();
        java.util.Arrays.sort(arr5);
        tb = System.currentTimeMillis();
        
        System.out.println(
                "java.util.Arrays.sort in: " 
                        + (tb - ta)
                        + " milliseconds.");
        
        boolean agree = java.util.Arrays.equals(arr1, arr2) &&
                        java.util.Arrays.equals(arr2, arr3) &&
                        java.util.Arrays.equals(arr3, arr4) &&
                        java.util.Arrays.equals(arr4, arr5);
        
        System.out.println("Sorts agree: " + agree);
    }
    
    private static Integer[] getRandomArray() {
        Random random = new Random(13L);
        Integer[] array = new Integer[ARRAY_LENGTH];
        
        for (int i = 0; i < array.length; ++i) {
            array[i] = random.nextInt();
        }
        
        return array;
    }
}

Typical output

Insertion sort in: 4090 milliseconds.
Bubble sort in:    12530 milliseconds.
Comb sort in:      37 milliseconds.
Shell sort in:     28 milliseconds.
java.util.Arrays.sort in: 45 milliseconds.
Sorts agree: true

Critique request

As always, I am eager to receive any constructive critique on my work.