At worst the binary search will require O(n log n) inspections of the array for all elements. But since that on average half of the elements of b need to be moved to insert a new element then the number of element visits is n² / 2 or O(n²), not as good as merge sort.