Insertion sort is a simple and efficient sorting algorithm that is used to sort small arrays or lists. It works by dividing the input list into two parts: the sorted part and the unsorted part. The sorted part is initially empty, and the unsorted part contains all the elements of the input list. The algorithm iterates through the unsorted part, picking one element at a time and inserting it into the correct position in the sorted part.
The algorithm starts by assuming that the first element of the input list is already sorted. It then picks the second element and compares it with the first element. If the second element is smaller than the first element, they are swapped. Otherwise, the second element is already in its correct position in the sorted part.
The algorithm then picks the third element and compares it with the second element. If the third element is smaller than the second element, they are swapped. If the third element is also smaller than the first element, it is swapped with the first element. Otherwise, it is already in its correct position in the sorted part.
The algorithm continues in this way, picking one element at a time and inserting it into the correct position in the sorted part. At each iteration, the sorted part grows by one element, and the unsorted part shrinks by one element. When the algorithm has iterated through all the elements in the unsorted part, the entire input list is sorted.
Insertion sort has a time complexity of O(n^2) in the worst case, where n is the number of elements in the input list. However, it has a best-case time complexity of O(n) when the input list is already sorted, and it is also efficient for small input sizes. Additionally, insertion sort is an in-place sorting algorithm, which means that it does not require any additional memory to perform the sort.
Insertion sort is a stable sorting algorithm, which means that it preserves the relative order of equal elements. This property is important in some applications, such as sorting database records by multiple columns.
In conclusion, insertion sort is a simple and efficient sorting algorithm that is useful for small input sizes and when the input list is partially sorted. Although it has a worst-case time complexity of O(n^2), it has a best-case time complexity of O(n) and is an in-place sorting algorithm. Furthermore, its stability property makes it useful in certain applications.
