in reply to Re^14: In-place sort with order assignment (runs)
in thread In-place sort with order assignment

O(0.5 * (N + U) * log N) and O(N log N) are the same

That's exactly what the last sentence in my previous post said!

So, for a set where O(N log U) is different from O(N log N), the chances of two random elements to be the same is actually pretty high.

Only for very degraded cases where there is an element that appears with probability near to 1.

Replies are listed 'Best First'.
Re^16: In-place sort with order assignment (runs)
by JavaFan (Canon) on Sep 22, 2010 at 10:15 UTC
    That's exactly what the last sentence in my previous post said!
    It was totally unclear to me that your last sentence referred to the first sentence of your post, and not to the sentence preceeding it.
[reply]

In Section Seekers of Perl Wisdom