sort complexity on nearly sorted input

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

Re: sort complexity on nearly sorted input

On Sat, Feb 11, 2012 at 10:20 AM, Peng Yu pengyu...@gmail.com 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

Re: sort complexity on nearly sorted input

On 02/11/2012 04:20 PM, Peng Yu wrote: 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,