Insertion Sort

To implement a program to sort a list of elements using the insertion sort algorithm.

Insertion sort is a simple sorting algorithm that works like the sorting of playing cards in hands.

Imagine you have a deck of cards in your hand, and you want to arrange them in ascending order. Here's how Insertion Sort works:

**Start with the first card:**Consider the first card in your hand as the "sorted" part.**Pick the next card:**Take the next card and compare it with the cards in the "sorted" part.**Insert into the correct position:**Insert the card into the correct position in the "sorted" part by shifting the larger cards to the right.**Repeat:**Repeat steps 2-3 for each remaining card until the entire deck is sorted.

Similarly, insertion sorting works by dividing a list into two parts: a sorted sub-list and an unsorted sub-list. Initially, the sorted sub-list contains only the first element of the list, and the unsorted sub-list contains the rest of the elements.

The algorithm iterates through the unsorted sub-list, taking one element at a time, and inserts it into its correct position in the sorted sub-list. To insert an element, the algorithm compares it with the elements in the sorted sub-list from right to left until it finds the correct position for the element.

The insertion sort algorithm has a time complexity of O(n^2) in the worst case and O(n) in the best case when the input list is already sorted.

Insertion sort is a stable sorting algorithm, meaning that it preserves the relative order of equal elements in the sorted list. It is also an in-place sorting algorithm, meaning that it does not require any additional memory for sorting.

Insertion sort is useful for sorting small to medium-sized lists or partially sorted lists. However, it is not efficient for sorting large lists due to its quadratic time complexity.

E.g. Initial list: [5, 2, 9, 1, 5]

**Pass 1: **

- Sorted: [5], Element to Insert: 2
- Compare 2 with 5 (shift 5 to the right).
- Insert 2 at the correct position.
- Result: [2, 5, 9, 1, 5]

**Pass 2: **

- Sorted: [2, 5], Element to Insert: 9
- Compare 9 with 5 (no shift needed).
- Insert 9 at the correct position.
- Result: [2, 5, 9, 1, 5]

**Pass 3: **

- Sorted: [2, 5, 9], Element to Insert: 1
- Compare 1 with 9 (shift 9 to the right).
- Compare 1 with 5 (shift 5 to the right).
- Compare 1 with 2 (shift 2 to the right).
- Insert 1 at the correct position.

Result: [1, 2, 5, 9, 5]

**Pass 4**:

- Sorted: [1, 2, 5, 9], Element to Insert: 5
- Compare 5 with 9 (shift 9 to the right).
- Compare 5 with 5 (shift 5 to the right).
- Insert 5 at the correct position.

Result: [1, 2, 5, 5, 9]

The final sorted list is [1, 2, 5, 5, 9]. This process of picking, comparing, and inserting continues until all elements are in their correct order.

- Understanding of sorting algorithms: Implementing the insertion sort algorithm requires an understanding of sorting algorithms, their time complexity, and their advantages and disadvantages.
- Familiarity with list manipulation: The insertion sort algorithm involves manipulating lists by shifting elements to make room for a new element to be inserted in its correct position. Implementing the insertion sort algorithm requires familiarity with lists manipulation techniques.
- Ability to implement algorithms: Implementing the insertion sort algorithm requires programming skills such as using loops, conditionals, and lists operations to perform the necessary computations.
- Ability to analyze algorithms: Analyzing the time complexity of the insertion sort algorithm can help students gain an understanding of algorithmic efficiency and the trade-offs between time and space complexity.
- Problem-solving skills: Implementing the insertion sort algorithm requires problem-solving skills to identify the inputs needed, the steps involved in the algorithm, and the output to be generated.