Insertion sort is one of the fundamental sorting algorithms in computer science. It works by maintaining a sorted portion at the beginning of the array and gradually expanding it by inserting elements from the unsorted portion into their correct positions. Let's visualize how this algorithm works with an example array.
Let's start with the first iteration. We begin with element 2, which is the first element in the unsorted portion. We compare it with element 5 in the sorted portion. Since 2 is less than 5, we need to shift 5 to the right and insert 2 at the beginning. After this step, our sorted portion contains 2 and 5, while the unsorted portion has 4, 6, 1, and 3.
Now we move to the second iteration with element 4. We compare 4 with the elements in the sorted portion. First, we compare 4 with 2. Since 4 is greater than 2, we continue. Next, we compare 4 with 5. Since 4 is less than 5, we need to insert 4 between 2 and 5. We shift 5 to the right and place 4 in its correct position. Our sorted portion now contains 2, 4, and 5.
Let's complete the sorting process. For element 6, since it's greater than 5, we simply place it at the end of the sorted portion. For element 1, it's smaller than all existing elements, so we insert it at the beginning. Finally, element 3 goes between 2 and 4. The insertion sort algorithm has a time complexity of O(n squared) in the worst case and O(1) space complexity, making it efficient for small datasets.