Insertion Sort – Sorting Algorithm

Insertion Sort

Insertion Sort is a simple and intuitive sorting algorithm. It builds the sorted portion of the array one element at a time by comparing and inserting elements into their correct position.

---

1. How It Works

1. Assume the first element is already sorted.
2. Start with the second element and compare it with the sorted portion of the array.
3. Insert the element into its appropriate position within the sorted portion.
4. Repeat the process for all elements until the entire array is sorted.

---

2. Characteristics

• Time Complexity:
  • Best Case: O(n) (if the array is already sorted)
  • Average/Worst Case: O(n^2)
• Space Complexity:
  • In-place sorting: O(1)
• Stable Sort:
  • Maintains the relative order of equal elements.

---

3. Example Process

Array: [12, 11, 13, 5, 6]

1. First Element: Already sorted → [12].
2. Second Element: 11
   • Compare with 12 and insert 11 before it → [11, 12].
3. Third Element: 13
   • 13 is larger than 12, so it stays in place → [11, 12, 13].
4. Fourth Element: 5
   • Compare with 13, 12, and 11, and insert 5 at the beginning → [5, 11, 12, 13].
5. Fifth Element: 6
   • Compare with 13, 12, and 11, and insert 6 before 11 → [5, 6, 11, 12, 13].

---

4. Advantages and Disadvantages

Advantages:

• Simple to implement and understand.
• Efficient for small datasets or nearly sorted data.
• Stable sort, which preserves the relative order of equal elements.

Disadvantages:

• Inefficient for large datasets due to O(n^2) time complexity.
• Slower compared to advanced algorithms like Merge Sort or Quick Sort for unsorted or large arrays.

---

5. Java Implementation

import java.util.Arrays;

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        int n = arr.length;

        for (int i = 1; i < n; i++) {
            // Store the current element
            int key = arr[i];
            int j = i - 1;

            // Move elements greater than key one position ahead
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }

            // Insert the current element at its correct position
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6};
        System.out.println("Original Array: " + Arrays.toString(arr));

        insertionSort(arr);

        System.out.println("Sorted Array: " + Arrays.toString(arr));
    }
}

---

6. Python Implementation

def insertion_sort(arr):
    # Traverse from the second element to the last
    for i in range(1, len(arr)):
        # Store the current element
        key = arr[i]
        j = i - 1

        # Shift elements that are greater than key to the right
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        
        # Place the key at its correct position
        arr[j + 1] = key

# Example usage
if __name__ == "__main__":
    arr = [12, 11, 13, 5, 6]
    print("Original Array:", arr)

    insertion_sort(arr)

    print("Sorted Array:", arr)

---

7. Optimizations

• Use Binary Search:
  To find the insertion position in the sorted portion, use binary search instead of linear search. However, this may compromise stability.
• Early Termination:
  If no shifts are needed during a pass, terminate the loop early (applicable for nearly sorted data).

---

8. Applications

Insertion Sort is used in scenarios where:

• The dataset is small.
• The dataset is already nearly sorted.
• Stability is required, and the relative order of elements with equal keys must be maintained.

While Insertion Sort is straightforward and useful for small or partially sorted datasets, it is inefficient for larger datasets. Advanced algorithms like Merge Sort, Quick Sort, or Heap Sort are better suited for large arrays.