InsertionSort in JAVA

Insertion sort is a simple comparison sorting algorithm that uses two pointers to reorder a set of unsorted numbers. Suppose there is a set of unsorted numbers. If the set contains only one number, then it is already sorted. If the set contains more than one numbers, then we start with the index 1 and iterate until the end of the list. For each iteration, we hold the value at the current index in a temp variable, iterating backward and shift the value of the inner loop forward by one index until the value of the inner loop is no longer greater than temp or the inner loop has reached the lower bound. This algorithm runs in O(n^2) time with constant space.

public static void insertionSort(int[] arr) {
    int n = arr.length;
    if (n == 0 || n == 1) return;

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

        while (j >= 0 && arr[j] > temp) {
            arr[j + 1] = arr[j];
            j--;
        }

        arr[++j] = temp;
    }
}

This article is my 13th oldest. It is 184 words long, and it’s got 0 comments for now.