Best Case, O(n)

Worst Case, Ω(n^2)

Memory Complexity, O(1)

import java.util.Random;
import java.util.Arrays;

public class Insertion
{
    //insertion sort	
    public static void insertionSort(int arr[])
    {
	int n = arr.length;
        for (int i=1; i<n; ++i)
        {
            int key = arr[i];
            int j = i-1;
 
	    /* Insert A[j] into the sorted sequence A[1 ... j-1]*/
            while (j>=0 && arr[j] > key)
            {
                arr[j+1] = arr[j];
                j = j-1;
            }
            arr[j+1] = key;
        }
    }

    //generate an array with random elements
    public static int [] getArray(int size)
    {
	    int [] array = new int[size];
	    Random r = new Random();

	    for(int i = 0; i < size; i++)
		    array[i] = r.nextInt(100);

	    return array;
    }

    //display an array
    public static void displayArray(int arr[])
    {
	    for(int e : arr)
		    System.out.printf("%5d", e);
	    System.out.println();
    }

    public static void main(String args[])
    {
	    long start, end;
	    int [] array;
	    int [] array2;
	    int size = 100000;

	    //create two same arrays
	    array = getArray(size);
	    array2 = Arrays.copyOf(array, array.length);

	    //sort a huge array with insertion sort
	    start = System.currentTimeMillis();
	    insertionSort(array);
	    end = System.currentTimeMillis();
	    System.out.printf("Bubble sort time: %10f%n", (end-start)/1000000.0);

	    //sort the array with build-in sort function in Arrays class
	    start = System.currentTimeMillis();
	    Arrays.sort(array2);
	    end = System.currentTimeMillis();
	    System.out.printf("Build-in sort time: %10f%n", (end-start)/1000000.0);

	    //validate insertion sort
	    if(Arrays.equals(array, array2))
		    System.out.println("Bubble sort is validated ...");
	    else
		    System.out.println("Bubble sort does not work correctly ...");
    }
}