Measured insertion sort speed is too fast

Question

I am speed testing various sorting algorithms in Java by feeding them arrays with randomly generated numbers, and I'm getting weird results for insertion sort.

I use System.nanoTime() to measure run time, and insertion sort has lower values than quick sort and merge sort even when sorting large arrays, which seems wrong. I'm seeing normal (slow) run time for bubble sort or selection sort in the program, so I think I'm improperly measuring insertionSort's speed but I'm not sure how:

public static int[] insertionSort(int[] array) {
    long startTime = System.nanoTime();

    int current;
    int innerIdx;

    int arrayLength = array.length;
    for (int idx = 1; idx < arrayLength; idx++) {
        // iterate through the array, happens just once
        current = array[idx];
        for (innerIdx = idx - 1; current < array[innerIdx] && innerIdx >= 0; innerIdx--) {
            // while current is "traveling" over larger values in array
            array[innerIdx + 1] = array[innerIdx];
            // shift the array elements over by 1 index
        }
        array[innerIdx + 1] = current;
    }

    long endTime = System.nanoTime() - startTime;
    System.out.println("Insertion Sort runtime (ns) = " + endTime);
    return array;
}

The following is the main method, which contains bubble and selection which seem to be measured properly (merge and quick are in separate classes):

import java.util.Random;
import java.util.Scanner;

public class Algorithms {

static boolean displayOutput = false;

public static void main(String[] args) {
    // TODO Auto-generated method stub
    Scanner scanner = new Scanner(System.in);
    System.out.println("How long do you want the test array? (give integer)");
    int lengthOfTestArray = scanner.nextInt();
    System.out.println("Generate random values between 1 and... (give integer)");
    int randomCeiling = scanner.nextInt();
    System.out.println("Display sorted arrays onto screen? ('true' or 'false')");
    displayOutput = scanner.nextBoolean();
    System.out.println("-~-~-~(╯ಠ_ರೃ)╯︵ ┻━┻ LET'S DO THIS! \n");
    // END INPUT, user has defined size of array and range for values

    int[] testArray = new int[lengthOfTestArray];
    for (int idx = 0; idx < testArray.length; idx++) {
        // generate an array of random numbers
        Random rand = new Random();
        testArray[idx] = rand.nextInt(randomCeiling) + 1;
    }

    // create copies for each of the sorting algorithms
    int[] bubbleArray = testArray;
    int[] selectionArray = testArray;
    int[] insertionArray = testArray;
    int[] quickArray = testArray;
    int[] mergeArray = testArray;

    bubbleArray = bubbleSort(bubbleArray);
    System.out.println("Bubble Sort:");
    for (int value : bubbleArray) {
        System.out.print(value + " ");
    }

    System.out.println("\n-----------------");

    selectionArray = selectionSort(selectionArray);
    System.out.println("Selection Sort Output:");
    if (displayOutput) {
        for (int value : selectionArray) {
            System.out.print(value + " ");
        }
    }

    System.out.println("\n-----------------");

    insertionArray = insertionSort(insertionArray);
    System.out.println("Insertion Sort Output");
    if (displayOutput) {
        for (int value : insertionArray) {
            System.out.print(value + " ");
        }
    }

    System.out.println("\n-----------------");

    Quicksort.run(quickArray);
    System.out.println("Quick Sort Output");
    if (displayOutput) {
        for (int value : quickArray) {
            System.out.print(value + " ");
        }
    }

    System.out.println("\n-----------------");

    Mergesort.run(quickArray);
    System.out.println("Merge Sort Output");
    if (displayOutput) {
        for (int value : mergeArray) {
            System.out.print(value + " ");
        }
    }

}

public static int[] bubbleSort(int[] array) {
    // bubble sort iterates through array, rearranging 2 at a time
    // currently makes it ASCENDING
    long startTime = System.nanoTime();

    int trailingNum = 0;
    int arrayLength = array.length;
    boolean flag = true;

    while (flag) {
        flag = false;
        for (int idx = arrayLength - 1; idx > 0; idx--) {
            if (array[idx] < array[idx - 1]) {
                trailingNum = array[idx];
                array[idx] = array[idx - 1];
                array[idx - 1] = trailingNum;
                flag = true;
            }
        }
    }

    long endTime = System.nanoTime() - startTime;
    System.out.println("Bubble Sort runtime (ns) = " + endTime);
    return array;
}

public static int[] selectionSort(int[] array) {
    // finds next element out of order, swaps with correct position
    // currently ASCENDING
    long startTime = System.nanoTime();

    int arrayLength = array.length;

    for (int idx = 0; idx < array.length; idx++) {
        int lastMinimum = 0;
        int lastMinimumIndex = 0;

        for (int innerIdx = idx; innerIdx < array.length; innerIdx++) {
            if (innerIdx == idx) {
                // if first iteration, set the minimum as first value
                lastMinimumIndex = innerIdx;
            }
            if (array[innerIdx] < array[lastMinimumIndex]) {
                // if value at position smaller than min index, replace
                lastMinimumIndex = innerIdx;
            }
            // loop exit with best min index starting from index of outer
        }

        if (idx != lastMinimumIndex) {
            // if minimum value is not at the current index
            int tempMin = array[lastMinimumIndex];
            array[lastMinimumIndex] = array[idx];
            array[idx] = tempMin;
        }
    }

    long endTime = System.nanoTime() - startTime;
    System.out.println("Selection Sort runtime (ns) = " + endTime);
    return array;
}

public static int[] insertionSort(int[] array) {
    long startTime = System.nanoTime();

    int current;
    int innerIdx;

    int arrayLength = array.length;
    for (int idx = 1; idx < arrayLength; idx++) {
        // iterate through the array, happens just once
        current = array[idx];
        for (innerIdx = idx - 1; current < array[innerIdx] && innerIdx >= 0; innerIdx--) {
            // while current is "traveling" over larger values in array
            array[innerIdx + 1] = array[innerIdx];
            // shift the array elements over by 1 index
        }
        array[innerIdx + 1] = current;
    }

    long endTime = System.nanoTime() - startTime;
    System.out.println("Insertion Sort runtime (ns) = " + endTime);
    return array;
}

}

Answer 1

// create copies for each of the sorting algorithms
int[] bubbleArray = testArray;
int[] selectionArray = testArray;
int[] insertionArray = testArray;
int[] quickArray = testArray;
int[] mergeArray = testArray;

This did not create copies, all the int[] variables point to THE SAME ARRAY. After you sort it once the other algorithms receive an already sorted array.

To create a copy use java.util.Arrays.copyOf(...) or java.lang.System.arrayCopy(...)