Introduction

• Insertion Sort is a simple comparison-based sorting algorithm used to arrange elements in ascending or descending order.
• It builds the sorted array one element at a time by inserting each element into its correct position.
• This process continues until all elements are placed in the correct order.

• Logic / Steps (Simple):
  1. Start from the second element of the array (consider the first element as sorted).
  2. Compare it with elements in the sorted portion to find its correct position.
  3. Shift all larger elements in the sorted portion one position to the right.
  4. Insert the current element into its correct position.
  5. Repeat the process for all elements until the entire array is sorted.

• Program:

  public class InsertionSortExample
  {
      public static void main(String[] args)
      {
          int[] arr = {50, 80, 30, 60, 10, 40, 20, 70};
  
          // Insertion Sort
          for (int i = 1; i < arr.length; i++)
          {
              int temp = arr[i];
              int j = i - 1;
  
              // Move elements of arr[0..i-1] that are greater than temp
              // to one position ahead of their current position
              while (j >= 0 && arr[j] > temp)
              {
                  arr[j + 1] = arr[j];
                  j--;
              }
              arr[j + 1] = temp;
          }
  
          // Print sorted array
          for (int no : arr)
          {
              System.out.print(no + " ");
          }
      }
  }

  Output:

  Sorted Array: 10 20 30 40 50 60 70 80

Important Points to Note :-

• Insertion Sort is a simple comparison-based sorting algorithm that builds the sorted array one element at a time by inserting each element into its correct position.
• It is stable by default (preserves the order of equal elements).
• It is adaptive; performs fewer comparisons if the array is already partially sorted.
• Insertion Sort follows the comparison and shifting approach.
• Efficient for small arrays or nearly sorted arrays; fewer swaps compared to Bubble Sort.
• Time Complexity for Insertion Sort:

  • Case	Description	No. of Comparisons	Time Complexity
    Worst Case	Array is in reverse order; maximum comparisons and shifts required.	n(n-1)/2	O(n²)
    Average Case	Elements are in random order; comparisons and shifts required for insertion.	n²/4	Θ(n²)
    Best Case	Array is already sorted; only one comparison per element.	n-1	Ω(n)

• Space Complexity:
  • O(1) → only a few variables used; no extra memory needed.