Insertion Sort in Java

Q: Write insertion sort in Java.

Java example: import java.util.Arrays; public class InsertionSort { static void insertionSort(int[] arr) { for (int i = 1; i = 0 && arr[j] > key) { arr[j + 1] = arr[j]; // shift larger elements right j--; } arr[j + 1] = key; } } public static void main(String[] args) { int[] arr = {12, 11, 13, 5, 6}; insertionSort(arr); System.out.println(Arrays.toString(arr)); // [5, 6, 11, 12, 13] } }

Q: What is the time complexity of insertion sort?

Best case: O(n), when the array is already sorted. Average and worst case: O(n 2 ), when the array is random or reversed. Space: O(1).

Q: Is insertion sort stable?

Yes. The condition arr[j] > key stops at equal elements, so an element is never moved in front of an equal one that came before it.

Q: Write insertion sort that sorts in descending order.

Java example: static void sortDescending(int[] arr) { for (int i = 1; i = 0 && arr[j] < key) { // only the comparison changes arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } }

Q: What is binary insertion sort?

It uses binary search to find where the next element belongs in the sorted part, reducing comparisons to O(n log n). The elements must still be shifted, so the total time remains O(n 2 ).

Q: How does insertion sort compare with bubble and selection sort?

All three are O(n 2 ) in the worst case, but insertion sort is usually the fastest of the three in practice: it does fewer writes than bubble sort, adapts to sorted input unlike selection sort, and is stable.

Insertion Sort in Java

Sorting is the process of arranging a list of unsorted data in a particular order, either ascending or descending. Sort algorithms play a very crucial role for organizing unsorted data and facilitating efficient searching, retrieval, and analysis.

Every sorting algorithm has a unique approach for sorting the data; these sorting algorithms are used according to the specific requirements of the problem, including data size, structure, and distribution, as well as time and space constraints.

In this tutorial, we are going to learn all about Insertion Sort in Java.

Java program for implementation of Insertion Sort

InsertionSortExample.java

public class InsertionSortExample {
  /* Function to sort an array using insertion sort technique */
  static void sortArray(int array[]) {
    for (int i = 1; i < array.length; ++i) {
      int key = array[i];
      int j = i - 1;

      /*
        * Move elements of array[0..i-1], that are greater than key,
        * to one position ahead of their current position
        */
      while (j >= 0 && array[j] > key) {
        array[j + 1] = array[j];
        j = j - 1;
      }
      array[j + 1] = key;
    }
  }

  // A function to print an array
  static void printArray(int array[]) {
    for (int i = 0; i < array.length; ++i)
      System.out.print(array[i] + " ");

    System.out.println();
  }

  public static void main(String args[]) {
    // Create an array
    int array[] = { 40, 70, 90, 20, 80, 100, 60, 10, 30, 50 };

    System.out.println("Created array elements: ");
    // Printing created array elements
    printArray(array);

    // Calling a method to sort an array
    sortArray(array);

    System.out.println("\nSorted array elements: ");
    // Printing sorted array elements
    printArray(array);
  }
}

Output

Created array elements:
40 70 90 20 80 100 60 10 30 50

Sorted array elements:
10 20 30 40 50 60 70 80 90 100

Frequently Asked Questions (FAQ)

Q1. How does insertion sort work?

Insertion sort builds a sorted section at the start of the array. It takes each next element and shifts larger sorted elements one place right until it finds the correct position, like sorting playing cards in your hand.

Q2. Write insertion sort in Java.

InsertionSort.java

import java.util.Arrays;

public class InsertionSort {

    static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];      // shift larger elements right
                j--;
            }
            arr[j + 1] = key;
        }
    }

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

Q3. What is the time complexity of insertion sort?

Best case: O(n), when the array is already sorted.
Average and worst case: O(n²), when the array is random or reversed.
Space: O(1).

Q4. Why is insertion sort fast on nearly sorted data?

Each element moves only as far as it is out of place. If every element is within a few positions of its final place, the inner loop runs only a few times per element, so the total work is close to O(n).

Q5. Is insertion sort stable?

Yes. The condition arr[j] > key stops at equal elements, so an element is never moved in front of an equal one that came before it.

Q6. Why do real sorting libraries use insertion sort?

For small arrays, insertion sort has very low overhead. Java's Arrays.sort for primitives (dual-pivot quicksort) and Collections.sort (TimSort) switch to insertion sort for small sections, typically fewer than about 32 to 47 elements.

Q7. Write insertion sort that sorts in descending order.

InsertionSortDescending.java

static void sortDescending(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] < key) {    // only the comparison changes
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

Q8. What is binary insertion sort?

It uses binary search to find where the next element belongs in the sorted part, reducing comparisons to O(n log n). The elements must still be shifted, so the total time remains O(n²).

Q9. Write a Java method that inserts one new value into an already sorted array.

InsertIntoSorted.java

// arr has room for one more element at index size
static void insertSorted(int[] arr, int size, int value) {
    int j = size - 1;
    while (j >= 0 && arr[j] > value) {
        arr[j + 1] = arr[j];
        j--;
    }
    arr[j + 1] = value;
}

This is exactly one step of insertion sort, and it shows why the algorithm suits data that arrives one item at a time.

Q10. How does insertion sort compare with bubble and selection sort?

All three are O(n²) in the worst case, but insertion sort is usually the fastest of the three in practice: it does fewer writes than bubble sort, adapts to sorted input unlike selection sort, and is stable.

Was this tutorial helpful?

Help Us Improve

Java program for implementation of Insertion Sort

Frequently Asked Questions (FAQ)