Insertion Sort Algorithm O n Best Case

What is Insertion Sort?

Insertion Sort is a simple sorting algorithm that builds the sorted portion of the array one element at a time. At each step, it takes the next element and inserts it into its correct position among the elements that are already sorted.

A common real-world analogy is sorting playing cards in your hand: you pick one card at a time and place it into the correct position among the cards already arranged.

Core Idea

Insertion Sort maintains two parts of the array:

For each new element, the algorithm shifts larger elements of the sorted portion one position to the right and inserts the element into the gap created.

a sorted portion on the left,
an unsorted portion on the right.

How Insertion Sort Works

Start from the second element because the first element by itself is already sorted.
Treat the current element as the key.
Compare the key with elements to its left.
Shift all larger elements one position to the right.
Insert the key at its correct position.
Repeat until the array is fully sorted.

Time and Space Complexity

The best case occurs when the array is already sorted, because each element is checked once and no shifting is needed. The worst case occurs when the array is reverse sorted, because each new key must be moved all the way to the front.

Case	Time	Space	Stable?
Best	O(n)	O(1)	Yes
Average	O(n^2)	O(1)	Yes
Worst	O(n^2)	O(1)	Yes

Why Insertion Sort Is Good for Nearly Sorted Data

Insertion Sort performs very well when the array is already sorted or almost sorted. In such cases, each element only needs a small number of comparisons and shifts, so the total running time becomes close to O(n).

This is why insertion sort is often used inside more advanced sorting algorithms for small or nearly sorted subarrays.

How it Works on an Example

Consider the array [12, 11, 13, 5, 6].

i = 1: key = 11. Shift 12 right, then insert 11. Result: [11, 12, 13, 5, 6]
i = 2: key = 13. It is already greater than 12, so it stays. Result: [11, 12, 13, 5, 6]
i = 3: key = 5. Shift 13, 12, and 11 right, then insert 5. Result: [5, 11, 12, 13, 6]
i = 4: key = 6. Shift 13, 12, and 11 right, then insert 6. Result: [5, 6, 11, 12, 13]

Insertion Sort Implementation

import java.util.Arrays;

public class InsertionSort {

    static void insertionSort(int[] arr) {
        int n = arr.length;

        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;

            // Shift larger elements to the right.
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }

            arr[j + 1] = key;
        }
    }

    static void insertionSortRec(int[] arr, int n) {
        if (n <= 1) return;

        insertionSortRec(arr, n - 1);

        int key = arr[n - 1];
        int j = n - 2;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6};
        System.out.println("Before: " + Arrays.toString(arr));
        insertionSort(arr);
        System.out.println("After:  " + Arrays.toString(arr));

        int[] sorted = {1, 2, 3, 4, 5};
        insertionSort(sorted);
        System.out.println("Sorted: " + Arrays.toString(sorted));
    }
}

Step-by-Step Trace

For the array [12, 11, 13, 5, 6]:

i	Key	Sorted Portion Before	Array After Insertion
1	11	[12]	[11, 12, 13, 5, 6]
2	13	[11, 12]	[11, 12, 13, 5, 6]
3	5	[11, 12, 13]	[5, 11, 12, 13, 6]
4	6	[5, 11, 12, 13]	[5, 6, 11, 12, 13]

Why Insertion Sort Is Stable

Insertion Sort is stable because equal elements are not moved past one another unnecessarily. If two values are equal, their original relative order is preserved.

This matters when sorting records by multiple fields.

Why Insertion Sort Is In-Place

Insertion Sort uses only a few extra variables such as the key and index counters. It does not need an extra array, so its space complexity is O(1).

Insertion Sort vs Bubble Sort vs Selection Sort

Feature	Insertion Sort	Bubble Sort	Selection Sort
Best case	O(n)	O(n)	O(n^2)
Average / Worst	O(n^2)	O(n^2)	O(n^2)
Stable	Yes	Yes	No
Good for nearly sorted data	Yes	Sometimes	No
Main strength	Fast for small and nearly sorted arrays	Simple concept	Minimum number of swaps

When to Use Insertion Sort

Avoid insertion sort for large random datasets because its average and worst-case times are quadratic.

Small arrays: low overhead makes it practical for tiny inputs.
Nearly sorted data: very efficient when only a few elements are out of place.
Online sorting: can process elements as they arrive.
As a helper in hybrid sorts: often used inside algorithms like Timsort or optimized Quick Sort.

Advantages of Insertion Sort

Easy to understand and implement.
Stable.
In-place.
Very good for small or nearly sorted input.
Works well for online sorting.

Limitations of Insertion Sort

Average-case time is O(n^2).
Worst-case time is O(n^2).
Not suitable for large random arrays.

Insertion Sort Failure Cases

Confusing insertion with swapping. The standard version mainly shifts elements, then inserts the key.
Forgetting that the first element is already considered sorted.
Assuming all simple sorts behave the same on nearly sorted input.
Using insertion sort on large random datasets where O(n^2) becomes expensive.

Insertion Sort Rules

Insertion Sort builds a sorted array one element at a time.
It is stable and in-place.
Its best case is O(n), which makes it strong on nearly sorted data.
Its average and worst cases are O(n^2).
It is most useful for small inputs and as a helper inside more advanced sorting algorithms.