N. wrote:

...

The way I figure it, instead of having the inner loop iterate back

through the already sorted array (which takes N-1 in worst-case),

couldn't binary search be used to find the position that the next int

is put in, hence taking the inner loop from some function of N to some

function in log N? Anyone have any details on how to do this?

It is not really about the search. It is about the insertion that follows.

While using binary search in place of direct iteration will improve the

performance of the implementation, the complexity will still remain at

O(N^2) level since the insertion itself requires O(N) time.

--

Best regards,

Andrey Tarasevich