Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.std.c++ > #428

Re: inplace_merge

Show all headers | View raw

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                      ]

Back to comp.std.c++ | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

inplace_merge dhruv<dhruvbird@gmail.com> - 2012-02-24 10:00 -0800
  Re: inplace_merge Daniel Krügler <daniel.kruegler@googlemail.com> - 2012-03-04 14:24 -0800
    Re: inplace_merge dhruv<dhruvbird@gmail.com> - 2012-03-05 11:17 -0800

csiph-web