Insertion Sort

Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time.
It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.
However, insertion sort provides several advantages:
- Simple implementation
- Efficient for (quite) small data sets
- Adaptive: efficient for data sets that are already substantially sorted
- More efficient in practice than most other simple quadratic (i.e., $O(n^2)$ ) algorithms such as selection sort or bubble sort
- Stable: does not change the relative order of elements with equal keys
- In-place: only requires a constant amount $O(1)$ of additional memory space
- Online: can sort a list as it receives it

Start at Index 1: Begin the process at the second element of the array (index 1).
Temporary Storage: Store the value at the current index in a temporary variable (e.g., temp).
Examine Elements to the Left:
- Compare elements to the left of the current index with the value in temp.
- If an element to the left is larger than temp, shift it to the right.
- Continue shifting elements until you find an element smaller than temp or reach the beginning of the array.
Insertion: Insert the value from temp into the created opening.
Repeat: Continue this process for each element in the array.

Analogy: Think of it as arranging a jigsaw puzzle, where you move sections to fit in a new piece.

Array Creation:
- Create an array of integers with unsorted values.
```
int[] array = {9, 1, 8, 2, 7, 3, 6, 5, 4};
```
Display Array Elements (Before Sorting):
- Use a for-each loop to print each element of the array.
```
for (int i : array) {
    System.out.print(i + " ");
}
```
Insertion Sort Function:
- Create a method named insertionSort that takes an integer array as a parameter.
```
private static void insertionSort(int[] array) {
    // Implementation
}
```
- Outer Loop:
  - Iterate over each element of the array, starting at index 1.
```
for (int i = 1; i < array.length; i++) {
    // Inner logic
}
```
- Temporary Variable:
  - Store the value at the current index i in a temporary variable temp.
```
int temp = array[i];
```
- Inner Loop (While Loop):
  - Create a variable j to track the element to the left of i.
```
int j = i - 1;
```
  - Compare values to the left of i and shift elements to the right as necessary.
```
while (j >= 0 && array[j] > temp) {
    array[j + 1] = array[j]; // Shift element to the right
    j--; // Decrement j
}
```
- Insertion:
  - Insert the value from temp into the created opening.
```
array[j + 1] = temp;
```
Display Array Elements (After Sorting):
- Call the insertionSort function and then print the sorted array using a for-each loop.

Runtime Complexity:
- The insertion sort algorithm has a runtime complexity of $O(n^2)$ , which is quadratic time.
- It is decent with small datasets but inefficient with large datasets.
Comparison:
- Insertion sort tends to be preferable to both bubble sort and selection sort.
- It uses fewer steps than bubble sort.
Best Case Scenario:
- In the best-case scenario, insertion sort can run in $O(n)$ linear time.
- Selection sort remains $O(n^2)$ even in the best-case scenario.
Adaptive: Efficient for data sets that are already substantially sorted
Stable: Does not change the relative order of elements with equal keys
In-place: Only requires a constant amount $O(1)$ of additional memory space