Re: STL implementation of list::sort
On 27 Aug., 13:30, Mathias Gaunard wrote:
On Aug 26, 12:04 am, SG wrote:
On 25 Aug., 19:25, Mathias Gaunard wrote:
On Aug 25, 6:26 am, Andy Venikov wrote:
Mathias Gaunard wrote:
It's O(nlogn) run time, O(1) memory usage.
If the implementation is recursive, then I believe it'll be
O(log(n)) space complexity.
Which would be silly, given that such a sort on lists can easily use
O(1) space.
Andy was talking about the recursion trace.
The call tree has a depth of O(log(n)).
And there's certainly nothing silly about that.
My point is that you do not need recursion. Granted, you do need
O(logn) space, in the form of an integer big enough to hold the
maximum size of the list, but it's really a O(1) from an
implementation point of view.
See the implementation of list::sort in libstdc++ for an example.
If by "from an implementation point of view" you mean list::sort
allocates a fixed amount of space for doing its work, then yes. But
this sort I'm looking at right now (libstdc++ from GCC 4.4.3) also
stops working if the list has more than 2^64 (or so) elements. Of
course, this is a limit you won't reach in practice, but that's not
how the big-O is defined. Big-O is about the asymtotic behaviour and I
don't see how a linked list can be sorted without additional O(log n)
space. Sure, log n is rather insignificant, and in practice you can
assume log n <= 64. But it's still log n.
Cheers!
SG
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]