Java insertion sorting

Insertion sort is a simple sorting algorithm that works by iterating through the elements of an array and inserting each element in its correct position in a sorted subarray.

Here is an example of insertion sort in Java:

public class Main {
    public static void main(String[] args) {
        int[] arr = {4, 2, 7, 1, 3};
        insertionSort(arr);
        System.out.println(Arrays.toString(arr)); // Outputs: [1, 2, 3, 4, 7]
    }

    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 example, the insertionSort() method takes an array of integers as input and sorts it in ascending order using insertion sort. The method starts by iterating through the elements of the array, starting from the second element. For each element, it stores the value in a temporary variable called key and compares it to the elements in the sorted subarray to the left. If it finds an element that is larger than key, it shifts the element to the right and continues the comparison. When it finds an element that is smaller than or equal to key, it inserts key in the correct position in the sorted subarray.

Insertion sort has a time complexity of O(n^2) in the worst case, making it less efficient than other sorting algorithms for large arrays. However, it is simple to implement and can be useful for sorting small arrays or partially sorted arrays.

For more information on insertion sort and other sorting algorithms, you can refer to the Java tutorial.