Sort-and-search

Insertion sort is a sorting algorithm that builds the sorted array one element at a time. It divides the array into a sorted portion and an unsorted portion. It iterates through the unsorted portion and compares each element with the elements in the sorted portion, shifting larger elements to the right. This process continues until the current element finds its correct position in the sorted portion. The algorithm repeats this for all elements, gradually building the sorted array. While insertion sort is simple and effective for small datasets or partially sorted data, it becomes less efficient for larger datasets due to its quadratic time complexity O(n^2).