Insertion Sort

Problem Solved

Insertion Sort solves the Sorting problem.

Design and Strategy

Insertion Sort works by dividing the array into two sections: a sorted portion on the left and an unsorted portion on the right. Initially, the sorted portion contains only the first element. The algorithm repeatedly takes the first element from the unsorted portion (called the key element) and inserts it into its correct position within the sorted portion. With each step, the sorted portion grows by one, and the unsorted portion shrinks by one, until the entire array becomes sorted. Thus, Insertion Sort is considered a decrease-and-conquer algorithm.

More formally, the algorithm works as follows:

1. Initially, consider the first element of the array (index 0) as the sorted portion.
2. Select the first element from the unsorted portion as the key element.
3. Starting from the end of the sorted portion, scan leftward through the array. As long as the current element is greater than the key, shift it one position to the right. Let s be the index of the last element compared that is less than or equal to the key, or -1 if no such element is found.
4. Insert the key into position s + 1.
5. Move the boundary separating the sorted and unsorted portions one position to the right, and repeat steps 2–5 until the array is fully sorted.

Code Implementations

public void insertionSort(int[] A) {
  for (int i = 1; i < A.length; i++) {
    int key = A[i];
    int j = i - 1;
    while (j >= 0 && A[j] > key) {
      A[j+1] = A[j];
      j--;
    }
    A[j+1] = key;
  }
}

void insertionSort(int []A, int n) {
  for (int i = 1; i < n; i++) {
    int key = A[i];
    int j = i - 1;
    while (j >= 0 && A[j] > key) {
      A[j+1] = A[j];
      j--;
    }
    A[j+1] = key;
  }
}

def insertion_sort(A):
  for i in range(1, len(A)):
    key = A[i]
    j = i - 1
    while j >= 0 and A[j] > key:
      A[j+1] = A[j]
      j -= 1
    A[j+1] = key
  return A

Time/Space Analysis

To analyze the complexity of Insertion Sort, we'll consider the worst-case scenario, where the array is initially sorted in descending order (completely reversed). This situation requires the maximum number of comparisons and shifts for each element, making it the worst-case scenario.

Insertion Sort builds the sorted array incrementally by repeatedly inserting the next element from the unsorted portion into the correct position within the already sorted portion on the left. Let's break down this process in detail:

• First iteration: The element at index 1 is compared with the element at index 0. In the worst case, it's smaller, requiring 1 comparison and 1 shift.
• Second iteration: The element at index 2 needs to be inserted into the sorted portion (indices 0-1). In the worst case, it is the smallest so far, requiring 2 comparisons and 2 shifts.
• Third iteration: Similarly, the element at index 3, in the worst case, requires 3 comparisons and 3 shifts, as it is again the smallest encountered.
• Subsequent iterations: This pattern continues, with the element at index k requiring k comparisons and k shifts in the worst case.

Thus, the total number of comparisons and shifts in the worst case can be expressed as the sum:

1 + 2 + 3 + ... + (n - 2) + (n - 1) = n(n - 1)/2 = O(n²)

Therefore, the worst-case time complexity of Insertion Sort is O(n²).

However, consider the best-case scenario—when the array is already sorted. In this case, each element from the unsorted portion (starting from index 1) only needs one comparison to verify it’s in the correct position. There are no shifts required:

• Each of the (n - 1) elements after the first one requires exactly 1 comparison and 0 shifts.

Thus, in the best case, the total number of comparisons is exactly (n - 1) = O(n).

This linear complexity in the best case makes Insertion Sort efficient for nearly sorted datasets, outperforming algorithms like Bubble Sort in such scenarios. Nevertheless, the average complexity remains quadratic, O(n²), making Insertion Sort generally less efficient than more advanced sorting methods (e.g., Merge Sort, Quicksort) for large datasets.

Space Complexity: Insertion Sort is an in-place sorting algorithm, requiring only a constant amount of extra space to hold variables for indexing and temporary storage during shifts. Hence, its space complexity is O(1).