Binary Insertion Sort

The straight insertion algorithm presented in the preceding section does a linear search to find the position in which to do the insertion. However, since the element is inserted into a sequence that is already sorted, we can use a binary search instead of a linear search. Whereas a linear search requires O(n) comparisons in the worst case, a binary search only requires comparisons. Therefore, if the cost of a comparison is significant, the binary search may be preferred.

Program  defines the BinaryInsertionSorter class. The BinaryInsertionSorter class extends the AbstractSorter class defined in Program . The framework of the sort method is essentially the same as that of the StraightInsertionSorter class.

  
Program: BinaryInsertionSorter class sort method.

Exactly, n-1 iterations of the outer loop are done (lines 6-21). In each iteration, a binary search search is done to determine the position at which to do the insertion (lines 8-18). In the iteration of the outer loop, the binary search considers array positions 0 to i (for ). The running time for the binary search in the iteration is . Once the correct position is found, at most i swaps are needed to insert the element in its place.

The worst-case running time of the binary insertion sort is dominated by the i swaps needed to do the insertion. Therefore, the worst-case running time is . Furthermore, since the algorithm only swaps adjacent array elements, the average running time is also (see Section ). Asymptotically, the binary insertion sort is no better than straight insertion.

However, the binary insertion sort does fewer array element comparisons than insertion sort. In the iteration of the outer loop, the binary search requires comparisons, for . Therefore, the total number of comparisons is

(This result follows directly from Theorem ).

The number of comparisons required by the straight insertion sort is in the worst case as well as on average. Therefore on average, the binary insertion sort uses fewer comparisons than straight insertion sort. On the other hand, the previous section shows that in the best case the running time for straight insertion is O(n). Since the binary insertion sort method always does the binary search, its best case running time is . Table  summarizes the asymptotic running times for the two insertion sorts.

Copyright © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.