Insertion Sort, which is a simple sorting algorithm. Imagine you're organising a row of books on a shelf. You start with one book, and then, for each new book, you find the right position for it by comparing it with the books you've already placed. This process is what we call insertion sort. Concept: Insertion Sort is a comparison-based sorting algorithm that works by dividing the list into two parts: a sorted part and an unsorted part. Initially, the sorted part contains just one element (the first element of the list). The algorithm then repeatedly picks the next element from the unsorted part and inserts it into the correct position in the sorted part. Steps of the Algorithm: 1. Start with the second element: Treat the first element as sorted. 2. Compare the element with the elements before it: Start comparing the current element with the ones that are already sorted, moving backward. 3. Shift elements if necessary: If the current element is smaller than the compared element, shift the compared element one position to the right. 4. Insert the element in the correct position: Once a smaller element or the beginning of the list is reached, insert the current element into its correct position. Time Complexity: • Best Case: O(n) when the list is already sorted. • Worst Case: O(n²) when the list is in reverse order. • Average Case: O(n²) because of the nested comparisons and shifts. Example: Sorting [20, 35, 40, 100, 3, 10, 15] using Insertion Sort We will now go through each pass of the insertion sort to sort the list [20, 35, 40, 100, 3, 10, 15]. • Initial List: [20, 35, 40, 100, 3, 10, 15] Pass 1: • Compare 35 with 20: No swap needed as 35 > 20. • List after Pass 1: [20, 35, 40, 100, 3, 10, 15] Pass 2: • Compare 40 with 35: No swap needed as 40 > 35. • List after Pass 2: [20, 35, 40, 100, 3, 10, 15] Pass 3: • Compare 100 with 40: No swap needed as 100 > 40. • List after Pass 3: [20, 35, 40, 100, 3, 10, 15] Pass 4: • Compare 3 with 100: Shift 100 to the right. • Compare 3 with 40: Shift 40 to the right. • Compare 3 with 35: Shift 35 to the right. • Compare 3 with 20: Shift 20 to the right. • Insert 3 at the beginning. • List after Pass 4: [3, 20, 35, 40, 100, 10, 15] Pass 5: • Compare 10 with 100: Shift 100 to the right. • Compare 10 with 40: Shift 40 to the right. • Compare 10 with 35: Shift 35 to the right. • Compare 10 with 20: Shift 20 to the right. • Insert 10 between 3 and 20. • List after Pass 5: [3, 10, 20, 35, 40, 100, 15] Pass 6: • Compare 15 with 100: Shift 100 to the right. • Compare 15 with 40: Shift 40 to the right. • Compare 15 with 35: Shift 35 to the right. • Compare 15 with 20: Shift 20 to the right. • Insert 15 between 10 and 20. • List after Pass 6: [3, 10, 15, 20, 35, 40, 100] Final Sorted List: [3, 10, 15, 20, 35, 40, 100] This process continues for each element, gradually building up the sorted portion of the list. The key idea is to insert each new element into the already sorted portion of the array by comparing it with elements from the right to the left and shifting larger elements to the right.