By combining binary search and insertion sort, a sorting method for small input size
Abstract
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 ...
Get Algorithms now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
