Explanation
- **Insertion Sort** is a simple sorting algorithm that builds the final sorted array one item at a time. It works by gradually taking each element from the unsorted portion and inserting it into its correct position within the sorted portion of the array.
-
-
Steps:
- The first element is considered already sorted.
- The next element is taken and inserted into the correct position in the sorted portion of the list.
- This process is repeated for each element until the entire list is sorted.
-
Time Complexity:
- Best Case (Already Sorted): O(n)
- Average and Worst Case (Unsorted List): O(n^2)**