How does the insertion sort algorithm work, and what is its time complexity?

Insertion sort is a simple sorting algorithm that works by iterating over the input array and repeatedly inserting each element into its correct position in a sorted portion of the array. The sorted portion of the array starts with the first element and grows by one element each iteration until the entire array is sorted.

The insertion sort algorithm can be summarized as follows:

Iterate over the unsorted array from the second element to the last element. For each element, compare it to the elements in the sorted portion of the array from right to left until the correct position is found. Insert the element into its correct position in the sorted portion of the array by shifting the elements to the right. Repeat steps 2-3 for the remaining unsorted elements.

Here is an example implementation of the insertion sort algorithm in Java:

public 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];
            j--;
        }
        arr[j + 1] = key;
    }
}

In this implementation, the insertionSort method takes an integer array as input and sorts it using the insertion sort algorithm. It iterates over the array from the second element to the last element, and for each element, it compares it to the elements in the sorted portion of the array from right to left until the correct position is found. It then inserts the element into its correct position by shifting the elements to the right.

The time complexity of the insertion sort algorithm is O(n²) in the worst case, where n is the size of the input array. This is because the algorithm performs one comparison and one shift operation for each element in the array, leading to a nested loop structure and a time complexity of O(n²). However, the best case time complexity is O(n) when the array is already sorted, and the average case time complexity is also O(n²), making it less efficient than other sorting algorithms such as quicksort and mergesort for large input sizes.