Re: sort complexity on nearly sorted input

[Davide Brini]

On Sat, 11 Feb 2012 10:20:11 -0600, Peng Yu <address@hidden> 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, 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?

The complexity of an algorithm provides an upper bound for the worst case
which holds regardless of how bad the input is. (on the other hand, the
actual operation *may* cost less, depending on the specific algorithm and
input).

BTW, I don't know what sorting method "sort" uses, but for most sorting
algorithms the complexity (that is, the number of comparisons the algorithm
has to make to sort the data) is O(N log(N)). (Simplifying a lot, "O(Y)"
is the notation to say "at most Y").

Quick sort is a special case among the popular sort algorithms, in that its
complexity is officially O(N^2) with an *average* complexity of O(N
log(N)), just like the others; it can be modified and forced to be O(N
log(N)), but the reward of doing that isn't usually worth the cost; in
practice, the "normal" version performs as good as or better than other
guaranteed O(N log(N)) algorithms.