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
