On Sat, Feb 11, 2012 at 10:20 AM, Peng Yu <[email protected]> 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
