Probably depends what you're doing with it, physically, but if you were running insertion sort manually it'd be very intuitive to do something like binary searc

Probably depends what you're doing with it, physically, but if you were running insertion sort manually it'd be very intuitive to do something like binary search to find the correct insertion point. That would make it O(n lg n).