Re: sort complexity on nearly sorted input

[Peng Yu]

On Sat, Feb 11, 2012 at 10:20 AM, Peng Yu <address@hidden> wrote:
> Hi,
>
> I assume the time complexity of 'sort' is log N, where N is the input size.
                                                                  ^
typo. Should be N log N
>
> 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



-- 
Regards,
Peng