Is the new standard requirement for the worst case behavior for
sort still O(N*N) (which supposes a quicksort implementation) or is
it changed to O(N*logN) due to resent progress in sorting algorithms?
See, for example, notes for the SGI implementation of sort at
"http://www.sgi.com/Technology/STL/sort.html#2"

It would be quite annoying to provide own implementation for sort
just to be sure about O(N*logN) bounds in any case...

--
Regards, Igor Boukanov.
igor.boukanov@fi.uib.no
http://www.fi.uib.no/~boukanov/
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

boukanov@sentef1.fi.uib.no (Igor Boukanov) writes:

>Is the new standard requirement for the worst case behavior for
>sort still O(N*N) (which supposes a quicksort implementation) or is
>it changed to O(N*logN) due to resent progress in sorting algorithms?

According to the Nov 97 draft, the worst case for `sort' is unspecified.
Only the average case complexity is specified, and even that is
"approximate".  However, a footnote mentions that if you are
concerned about the worst case, you can use `stable_sort'
or `partial_sort'.  For `stable_sort', the draft specifies
a worst case of O(N * log N) comparisons.

--
Fergus Henderson <fjh@cs.mu.oz.au>   WWW: <http://www.cs.mu.oz.au/~fjh>
Note: due to some buggy software and a (probably accidental)
denial-of-service attack, any mail sent to me or comp.std.c++ between
 Tue Nov 25 20:00:00 UTC (6am Wed, local time)
and Wed Nov 26 06:00:00 UTC (4pm, local time)
may have gone into the bit-bucket.  Please re-send it.
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

boukanov@sentef1.fi.uib.no (Igor Boukanov) writes:

> Is the new standard requirement for the worst case behavior for
> sort still O(N*N) (which supposes a quicksort implementation) or is
> it changed to O(N*logN) due to resent progress in sorting algorithms?
> See, for example, notes for the SGI implementation of sort at
> "http://www.sgi.com/Technology/STL/sort.html#2"
>
> It would be quite annoying to provide own implementation for sort
> just to be sure about O(N*logN) bounds in any case...

The standard does not guarantee O(N log(N)) worst case behavior.
There's no longer any reason for worst-case behavior to be any worse
than that, though, since there is now a known O(N log(N)) algorithm
that is just as fast as quicksort on average.

The introsort algorithm was discovered too recently for the standard
to be changed, but you should expect that a good implementation will
use it.
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]