Sort Algorithm - Insertion Sort

Definition

Insertion sort is a straightforward comparison-based sorting algorithm that builds the final sorted array one element at a time. It iterates through the input array, taking each element and inserting it into its correct position within the already sorted portion of the array. This sorting method has an average and worst-case time complexity of O(n^2), making it less efficient than more advanced sorting algorithms for large datasets.

Code

public class InsertionSort {
    public static void main(String[] args) {
        // Create an array of integers
        int[] arr = {101, 1, 98, 35};

        // Call the insertionSort function to sort the array
        insertionSort(arr);

        // Print the sorted array
        System.out.println(Arrays.toString(arr));
    }

    public static void insertionSort(int[] arr) {
        // Iterate through the array starting from the second element
        for (int i = 1; i < arr.length; i++) {
            int insertVal = arr[i];       // Store the current element to be inserted
            int insertIndex = i - 1;      // Initialize the index to the left of the current element

            // Move elements greater than the current element to the right
            // until the correct position for the current element is found
            // be aware of the boundary conditions
            while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }

            // Place the current element in its correct position
            if (insertIndex != i) {
                arr[insertIndex + 1] = insertVal;
            }
        }
    }

}