Overview
Insertion Sort is a simple and intuitive sorting algorithm that builds the final sorted array one
element at a time. It operates by dividing the list into a sorted and an unsorted part. Initially,
the sorted part contains just the first element, and the rest of the list is unsorted. The algorithm
repeatedly picks the next element from the unsorted part and inserts it into the correct position
within the sorted part, shifting elements as necessary.
Time Complexity:
Best case: O(n) - When the list is already sorted, as no elements need to be moved.
Average case: O(n²) - The number of shifts increases as the list size grows, especially when
elements are randomly ordered.
Worst case: O(n²) - When the array is initially in reverse order, requiring maximum shifting.
Space Complexity: O(1) - It is an in-place sorting algorithm.
for i = 1 to length(list) - 1 key = list[i] j = i - 1 while j >= 0 and list[j] > key list[j + 1] = list[j] j -= 1 list[j + 1] = keySHORT EXPLANATION------------------1. Start from the second element (index 1)2. The current element is called 'key'3. Compare the key with elements before it4. Shift elements larger than the key to the right5. Insert the key in its correct position6. Repeat this process until the list is sorted7. The algorithm ensures the left portion of the list is always sorted