Explanation

• Concept: Insertion sort is a simple comparison-based sorting algorithm that builds the final sorted array one element at a time by repeatedly inserting the next element into the correct position.
• Process: Insertion sort iterates through the array, growing the sorted portion one element at a time by inserting the next element into its correct position.
• Steps:
  • Start with the first element as the sorted portion.
  • Take the next element and insert it into the sorted portion in the correct position.
  • Repeat the process for each element until the entire array is sorted.
• Efficiency: Insertion sort has a time complexity of O(n^2) for the worst and average cases, making it inefficient for large datasets. However, it is efficient for small datasets and nearly sorted arrays.

Python Implementation

      
          from typing import List

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

def run_algo():
    arr = [int(x) for x in input("Enter array (space separated): ").split()]
    sorted_arr = insertion_sort(arr)
    print("Sorted array:", sorted_arr)

if __name__ == "__main__":
    run_algo()

        

Test Cases

• Random Order

  Input:

  • Array: [64, 25, 12, 22, 11]
  • Target:

  Expected Output: [11, 12, 22, 25, 64]

  Explanation: The input array [64, 25, 12, 22, 11] is sorted in ascending order.

• Already Sorted

  Input:

  • Array: [11, 12, 22, 25, 64]
  • Target:

  Expected Output: [11, 12, 22, 25, 64]

  Explanation: The input array is already sorted, so the output remains the same.

• Reverse Order

  Input:

  • Array: [64, 25, 22, 12, 11]
  • Target:

  Expected Output: [11, 12, 22, 25, 64]

  Explanation: The input array [64, 25, 22, 12, 11] is sorted in ascending order.

• Single Element

  Input:

  • Array: [42]
  • Target:

  Expected Output: [42]

  Explanation: A single element array is already sorted.

• Empty Array

  Input:

  • Array: []
  • Target:

  Expected Output: []

  Explanation: An empty array remains empty after sorting.

Python Test Cases Implementation

          def run_tests():
    tests = [
        {"input": [64, 25, 12, 22, 11], "expected": [11, 12, 22, 25, 64]},
        {"input": [11, 12, 22, 25, 64], "expected": [11 ,12, 22, 25, 64]},
        {"input": [64, 25, 22, 12, 11], "expected": [11, 12, 22, 25, 64]},
        {"input": [42], "expected": [42]},
        {"input": [], "expected": []},
    ]
    for i, test in enumerate(tests, 1):
        result = insertion_sort(test["input"])
        assert result == test["expected"], f"Test {i} failed: Expected {test['expected']}, got {result}"
        print(f"Test {i} passed.")
if __name__ == "__main__":
    run_tests()