sort complexity on nearly sorted input

[Peng Yu]

Hi,

I assume the time complexity of 'sort' is log N, where N is the input size.

But I'm not familiar with 'sort' enough to tell the complexity of
sorting a nearly sorted input. Suppose that I have a listed of N
numbers, there only k numbers (k << N, say k=N/100) that are not in
the correct position and all the other N-k numbers are in the correct
position. Does anybody knows the time complexity of this case, or it
is still log N?

-- 
Regards,
Peng