| TOPIC: Insertion Sort | |
| DEFINITION: Insertion sort is a simple sorting algorithm that works by dividing the input into a sorted and an unsorted region, and then iteratively inserting elements from the unsorted region into the sorted region in the correct position. This process continues until the entire input is sorted, solving the problem of arranging elements in ascending or descending order. It's a straightforward and intuitive method for sorting small datasets. | |
| TIME_COMPLEXITY: The time complexity of insertion sort is O(n^2) in the worst and average cases, where n is the number of elements being sorted, because in the worst case, each element must be compared with every other element. However, in the best case, when the input is already sorted, the time complexity is O(n) because only one comparison per element is needed. | |
| SPACE_COMPLEXITY: The space complexity of insertion sort is O(1) because it only uses a constant amount of additional space to store temporary variables, and it sorts the input in-place, without requiring any extra space that scales with the input size. | |
| USE_WHEN: Insertion sort is a good choice when the input size is small, or when the input is nearly sorted, as it has a simple implementation and performs well in these scenarios. It's also a good choice when memory is limited, as it only uses a constant amount of extra space. | |
| AVOID_WHEN: Insertion sort is a poor choice for large datasets, as its quadratic time complexity makes it inefficient compared to other sorting algorithms like quicksort or mergesort, which have average-case time complexities of O(n log n). | |
| EXAMPLE: | |
| Initial array: [5, 2, 8, 3] | |
| -> Insert 2 into sorted [5]: [2, 5, 8, 3] | |
| -> Insert 8 into sorted [2, 5]: [2, 5, 8, 3] | |
| -> Insert 3 into sorted [2, 5, 8]: [2, 3, 5, 8] | |
| Result: [2, 3, 5, 8] | |
| REAL_WORLD_ANALOGY: Insertion sort is similar to how you might sort a hand of cards, by taking each card and inserting it into the correct position among the cards you've already sorted. | |
| SOURCE_NOTE: |