STL implementation of list::sort
Awashesh Kumar
Since list has bidirectional iterator so any of the random access
iterator based sorting algorithms (heap sort, quick sort etc) can not
be applied on lists. Still the complexity of list::sort is NlogN. So
which algorithm does it apply? I tried to look at algorithm.h where
some sort algos use introsort ( a mix of quick and heap sort) , but
still could not get how it is done for list. There is one way which I
can think of the way STL might implement list::sort is that is copies
list elements into a vector , applies any NlogN algo to sort the
elements and copies back the list. Any other thoughts on efficiency
of sorting on list??
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Ulrich Eckhardt
> Since list has bidirectional iterator so any of the random access
> iterator based sorting algorithms (heap sort, quick sort etc) can not
> be applied on lists.
I wouldn't say that quick sort (not sure about heap sort) requires random
access. Actually, a typical implementation using a linked list is much more
suitable for sorting because reordering just involves fiddling pointers,
not use of things like swap() or even deep copying.
Uli
--
Sator Laser GmbH
Geschäftsführer: Thorsten Föcking, Amtsgericht Hamburg HR B62 932
Mathias Gaunard
> I was wondering how is list member function sort implemented in STL.
> Since list has bidirectional iterator so any of the random access
> iterator based sorting algorithms (heap sort, quick sort etc) can not
> be applied on lists. Still the complexity of list::sort is NlogN. So
> which algorithm does it apply?
In-place merge sort.
It's O(nlogn) run time, O(1) memory usage.
Kaba
> I was wondering how is list member function sort implemented in STL.
Probably by merge sort. See for example:
http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html
Jeremy
> Awashesh Kumar wrote:
> > Since list has bidirectional iterator so any of the random access
> > iterator based sorting algorithms (heap sort, quick sort etc) can not
> > be applied on lists.
>
Would a sort member function need to use iterators at all? Why
couldn't the std::list just use a nlogn, in-place sorting algorithm
like quick or heap.
--
sjho...@dialrem.pipexrem.corem.ukrem
>I was wondering how is list member function sort implemented in STL.
>Since list has bidirectional iterator so any of the random access
>iterator based sorting algorithms (heap sort, quick sort etc) can not
>be applied on lists.
There is a quick sort for single and double linked lists.
There is also a merge sort for single and double linked lists which can be stable
(a requirement for std::list).
merge sort for linked lists can be implemented using just bidrectional iterators.
These are all O(N * log N).
They are _VERY_ efficient
In both cases the links are updated and the elements do not move.
So no copy constructors, destructors or assignment operators fire for the elements
that std::list is managing.
--- news://freenews.netfront.net/ - complaints: ne...@netfront.net ---
Andy Venikov
> On Aug 12, 2:04 pm, Awashesh Kumar <awashesh.ku...@gmail.com> wrote:
>> I was wondering how is list member function sort implemented in STL.
>> Since list has bidirectional iterator so any of the random access
>> iterator based sorting algorithms (heap sort, quick sort etc) can not
>> be applied on lists. Still the complexity of list::sort is NlogN. So
>> which algorithm does it apply?
>
> In-place merge sort.
>
> 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.
Mathias Gaunard
> 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.
Of course, all the standard does is mandate a O(n logn) runtime and a
stable sort.
nm...@cam.ac.uk
Mathias Gaunard <louf...@gmail.com> wrote:
>On Aug 25, 6:26 am, Andy Venikov <swojchelo...@gmail.com> 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.
No, it's not, but it is extremely unlikely that most C++ systems
would use the techniques where it would be useful.
C++ does not actually forbid the STL to use multiple threads, though
it would be quite hairy to implement, especially in C++0X. Such an
implementation would necessarily need more space. And, before you
deny this, there is already at least one parallel implementation
of the STL - see http://tech.unige.ch/omptl/
Regards,
Nick Maclaren.
SG
> 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)).
Cheers!
SG
Mathias Gaunard
> 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)).
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.
SG
> 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
Marc
> 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.
Actually, before talking big-Os, you need to define what you are
talking about. It is a fairly common model of computation where
registers are assumed to have at least log(n) bits (pointers can
address the entire memory), and if you count the size in terms of
number of registers...
What you describe is also perfectly true, in a different model.
What model is most relevant is too close to vi vs emacs to discuss
right now...
nm...@cam.ac.uk
Marc <marc....@gmail.com> wrote:
> On 27 aoűt, 23:22, SG <s.gesem...@gmail.com> wrote:
>> 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.
>
> Actually, before talking big-Os, you need to define what you are
> talking about. It is a fairly common model of computation where
> registers are assumed to have at least log(n) bits (pointers can
> address the entire memory), and if you count the size in terms of
> number of registers...
>
> What you describe is also perfectly true, in a different model.
>
> What model is most relevant is too close to vi vs emacs to discuss
> right now...
With one proviso, which IS relevant to C++'s specification. That
classic model (and it predates the rise of register architectures)
was accepted by its inventors to be an engineering approximation.
In particular, it is not mathematically self-consistent, and it
produces time complexities that are reliable only to within a
factor of about O(log(N)).
The denial of this leads to the lunatic dogma that radix sort is
O(N), whereas all comparison sorts are O(Nlog(N)). There ARE true
O(1) sorts, but only for certain classes of data.
I am not absolutely certain whether it can or does lead to space
inconsistencies of the same order. Anyway, the summary is that it
is a mistake to make too much fuss about mere O(log(N)) factors,
when using that model or any similar one.
Regards,
Nick Maclaren.
SG
> On 27 aoűt, 23:22, SG wrote:
>
>> 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.
>
> Actually, before talking big-Os, you need to define what you are
> talking about. It is a fairly common model of computation where
> registers are assumed to have at least log(n) bits (pointers can
> address the entire memory), and if you count the size in terms of
> number of registers...
>
> What you describe is also perfectly true, in a different model.
If if I treat the size of a pointer or register to be constant for all
list sizes n (which I actually do!), the list sort requires O(log n)
additional space. That was my point. It's not about register size. You
need to remember O(log n) pointers during the sort. You can do this
via recursion or via an iterative algorithm. Doesn't matter. You need
to remember O(log n) pointers at some point in the algorithm.
Cheers!
SG
Marc
> If if I treat the size of a pointer or register to be constant for all
> list sizes n (which I actually do!), the list sort requires O(log n)
> additional space. That was my point. It's not about register size. You
> need to remember O(log n) pointers during the sort. You can do this
> via recursion or via an iterative algorithm. Doesn't matter. You need
> to remember O(log n) pointers at some point in the algorithm.
Oops, sorry. I read Matthias' "you do need O(logn) space, in the form
of an integer big enough to hold the maximum size of the list" and
replied without checking. You are right that libstdc++ reserves 64
(approximation of log(n)) pointers, in a natural imperative version of
the recursive algorithm.
Now this extra storage is not necessary, you can do with only a
constant number of pointers, but the (constant factor) running-time
overhead is likely to make it unpractical compared to such a small
extra storage.