By combining binary search and insertion sort, a sorting method for small input size
Bhawnesh Kumar, Aditya Bhatt, Neeraj Panwar · Algorithms · 2024
Insertion sort, one of the popular sorting methods having average time complexity O(n2), is based on the decrease and conquer strategy. We insert elements one by one in the sorted part and decrease the size of the unsorted portion, instead of a simple comparison method for insertion of elements in the sorted portion if we apply the binary search approach to locate the appropriate position for the inserting element in the sorted part. This will reduce the number of key comparisons; the only problem with this approach is to shift the elements one place to its right which are greater than A[i]. But the convergence of this approach toward the result is fast than the simple insertion sort. As far as time complexity is concerned both have almost similar performance, but when the cost of comparison is high this method is well suited.