Hello,

Reading some of the comments in:
http://groups.google.com/group/comp.std.c++/browse_thread/thread/a0634f093aadc568/26a21cd2716afcae?lnk=gst&q=inplace_merge

IIRC, inplace_merge has a big-Oh O(n log n) (worst case) and this is
the case where it does NOT use any extra memory proportional to f(n)
(for some 'f'). If it is allowed to use O(n) memory, only then is the
running time O(n). This is much more expensive when compared to the
standard merge() that uses extra space.

There are known algorithms that can merge 2 sequences in O(n) worst
case time w/o using extra space. Why aren't we using them?

Also, I think that by using O(log n) extra space (for the recursion),
inplace_merge could be implemented entirely using Forward Iterators
(need to think more about this though).

Here is the reference to the relevant paper on in place merging in
linear time: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.8523


--
[ comp.std.c++ is moderated.  To submit articles, try posting with your ]
[ newsreader.  If that fails, use mailto:std-cpp-submit@vandevoorde.com ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Am 24.02.2012 19:00, schrieb dhruv:
>
> Hello,
>
> Reading some of the comments in:
> http://groups.google.com/group/comp.std.c++/browse_thread/thread/a0634f093aadc568/26a21cd2716afcae?lnk=gst&q=inplace_merge
>
> IIRC, inplace_merge has a big-Oh O(n log n) (worst case) and this is
> the case where it does NOT use any extra memory proportional to f(n)
> (for some 'f'). If it is allowed to use O(n) memory, only then is the
> running time O(n). This is much more expensive when compared to the
> standard merge() that uses extra space.
>
> There are known algorithms that can merge 2 sequences in O(n) worst
> case time w/o using extra space. Why aren't we using them?


Note that a conforming implementation *could* use them, so this seems
not a specification defect to me. The more interesting question is
whether such complexity constraints should be *required* for
implementations. To make such a proposal it would be helpful to have
an overview of existing implementations. Have you found any that does
implement the new forms?

The library specification is in principle flexible in this regard. One
example for a more stringent specification was that of std::sort,
which was in C++03 allowed to be O(N log N) *on average* with worse
worst case complexity. This freedom has been eliminated now, but that
was also decided on the fact that existing implementations were
already implementing the newer forms.

> Also, I think that by using O(log n) extra space (for the recursion),
> inplace_merge could be implemented entirely using Forward Iterators
> (need to think more about this though).


If you would like to open a library defect for this, you can post an
issue to the email address mentioned in the beginning of

http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html

It would presumably be helpful to provide an example implementation
demonstrating the idea, because such changes in the standard are
typically based on existing practice.

HTH & Greetings from Bremen,

Daniel Kr   gler


--
[ comp.std.c++ is moderated.  To submit articles, try posting with your ]
[ newsreader.  If that fails, use mailto:std-cpp-submit@vandevoorde.com ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

On Mar 4, 5:24 pm, Daniel Kr   gler<daniel.krueg...@googlemail.com>
wrote:
>  Am 24.02.2012 19:00, schrieb dhruv:
>
>  >  There are known algorithms that can merge 2 sequences in O(n) worst
>  >  case time w/o using extra space. Why aren't we using them?
>
>  Note that a conforming implementation *could* use them, so this seems
>  not a specification defect to me. The more interesting question is
>  whether such complexity constraints should be *required* for
>  implementations. To make such a proposal it would be helpful to have
>  an overview of existing implementations. Have you found any that does
>  implement the new forms?

There is no standard library (or other standard library in any other
language that I am aware of) that implements this. In fact, not many
people seem to know of this algorithm!

Here is the correct link - I posted a wrong link earlier:
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.88.1155

Basically, the constant increases from ~2 to ~4 with this
implementation. This doesn't necessarily mean doubling of the running
time though.

In fact, I would rather have another function called
"linear_inplace_unstable_merge" so that the user knows exactly what is
being provided.

>
>  The library specification is in principle flexible in this regard. One
>  example for a more stringent specification was that of std::sort,
>  which was in C++03 allowed to be O(N log N) *on average* with worse
>  worst case complexity. This freedom has been eliminated now, but that
>  was also decided on the fact that existing implementations were
>  already implementing the newer forms.

This sounds reasonable to me.

>
>  >  Also, I think that by using O(log n) extra space (for the recursion),
>  >  inplace_merge could be implemented entirely using Forward Iterators
>  >  (need to think more about this though).
>
>  If you would like to open a library defect for this, you can post an
>  issue to the email address mentioned in the beginning of
>
>  http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html
>
>  It would presumably be helpful to provide an example implementation
>  demonstrating the idea, because such changes in the standard are
>  typically based on existing practice.

Sure!


Regards,
-Dhruv.


--
[ comp.std.c++ is moderated.  To submit articles, try posting with your ]
[ newsreader.  If that fails, use mailto:std-cpp-submit@vandevoorde.com ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]