Insertion Sort
Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It iterates through the input elements, growing a sorted sub-array at the beginning of the array. For each new element, insertion sort finds the location within the sorted sub-array where the element belongs and inserts it there. It repeats until all input elements have been inserted into their correct position.
Let's say we have the array [5, 2, 4, 6, 1, 3].
1. Start with [5]. This is trivially sorted.
2. Insert 2: Compare 2 with 5. Since 2 < 5, insert 2 before 5. Array: [2, 5].
3. Insert 4: Compare 4 with 5. Since 4 < 5, shift 5 to the right. Compare 4 with 2. Since 4 > 2, insert 4 after 2. Array: [2, 4, 5].
4. Insert 6: Compare 6 with 5. Since 6 > 5, insert 6 after 5. Array: [2, 4, 5, 6].
5. Insert 1: Compare 1 with 6, 5, 4, and 2. Since 1 is smaller than all of them, insert 1 at the beginning. Array: [1, 2, 4, 5, 6].
6. Insert 3: Compare 3 with 6, 5, 4. Since 3 < 4, shift 4, 5, 6 to the right. Compare 3 with 2. Since 3 > 2, insert 3 after 2. Array: [1, 2, 3, 4, 5, 6].Insertion sort is an in-place, stable sorting algorithm. It has a time complexity of O(n^2) in the average and worst cases, making it inefficient for sorting large arrays. However, it performs well for small arrays or nearly sorted arrays, where its time complexity approaches O(n). In the best case (array is already sorted), insertion sort has a time complexity of O(n). The space complexity is O(1) because it sorts the array in-place.