Why is the worst-case binary selection sort time complexity considered O(n^2)?

Question

Wikipedia and other textbooks reference binary selection sort's asymptotic worst-case time complexity to be O(n^2), usually justifying this with any extra computation caused by swaps. I don't understand how this is derived

Pseudocode is below, assume binarysearch(array, n , lo , hi) -> index of placement

   input arr
   mid := arr[(len(arr) -1 )//2]
   sortarr := [mid]
   for each val in arr:
        index := binarysearch(sortarr,val,0,len(sortarr))
        insert val into sortarr at index
   return sortarr

The time complexity of binarysearch() is indiscriminately log(n). The for loop will iterate n times, hence you would expect the worst-case time complexity to be O(nlogn). What am I missing?

Answer 1

It is true that the time complexity of binary search is O(log n), but inserting into an array at an arbitrary position can take linear time in the size of the array, as all elements after the insertion point need to be shifted.