Insertion Sort of O(n^2) complexity and using Binary Search on previous values to improve complexity

Question

How would the algorithm's (of Insertion Sort of O(n^2)) complexity change if you changed the algorithm to use a binary search instead of searching previous values until you found where to insert your current value. Also, When would this be useful?

Answer 1

Your new complexity is still quadratic, since you need to move all of the sorted parts rightward. Therefore, using binary search is only marginally better.

I would recommend a fast sorting algorithm (in O(n log n) time) for large arrays, the quadratic insertion sort algorithm is suited only for small arrays.