To implement a program to sort a list of elements using insertion sort algorithm.
Insertion sort is a simple sorting algorithm that works by dividing an array into two parts: a sorted sub-array and an unsorted sub-array. Initially, the sorted sub-array contains only the first element of the array, and the unsorted sub-array contains the rest of the elements.
The algorithm iterates through the unsorted sub-array, taking one element at a time, and inserts it into its correct position in the sorted sub-array. To insert an element, the algorithm compares it with the elements in the sorted sub-array from right to left until it finds the correct position for the element.
The insertion sort algorithm has a time complexity of O(n^2) in the worst case and O(n) in the best case when the input array is already sorted. It has a space complexity of O(1) since it does not use any additional memory.
Insertion sort is a stable sorting algorithm, meaning that it preserves the relative order of equal elements in the sorted array. It is also an in-place sorting algorithm, meaning that it does not require any additional memory for sorting.
Insertion sort is useful for sorting small to medium-sized arrays or partially sorted arrays. However, it is not efficient for sorting large arrays due to its quadratic time complexity.