I'm a little too brain dead at the moment to follow the details of your algorithm, but for a crude upper limit of the complexity you can take it as a Merge Sort where you're starting part of the way through. You've already assembled from pairs back up to G lists of size GSize. So if you were doing a full up Merge Sort on N elements you'd be O(NlogN), but you've already done a bunch of it, so you're reducing it by G(Gsize log Gsize), giving you something like

O((NlogN)-G(Gsize log Gsize))

as an upper limit.(Ignoring for the moment the in-place issue)

These guys (Huang and Langston, who are ref 17 in your more dense paper) are a little bit easier to follow and claim that their in-place algorithm is O(N). They say less than 2N, so it's probably linear, or only slightly worse, and your ref gives you something like the sum (where I'm abbreviating Gsize as s for readability):

s log s + (s log (2s /s + 1)) + (s log (3s /s + 1))... up to the integer in the log getting to N/G, which looks like it reduces to:

=O(s log s + (s log (3)) + (s log (4))...(s log (N/G)))

where the sum is assuming you merge one pair of your subsets together, then merge in the next one (so you've got length s and 2s, then length s and 3s, up until you've done them all.

=O(s (Sum (log 1..N/G)))

=O(s log((N/G)!))

which doesn't look so bad-- it's better than NlogN and if you substitute back in s=N for the length of a single G=1, you end up back with NlogN, so it might be about right.

(I think... I probably did something wrong along the way and will want to strike this out later...but after this bit of exercise I might be able to wade through your algorithm, too...)

Edit: Huang and Langston isn't quite in place-- it uses a constant extra buffer, as does your Symvonis reference.

another edit to wrap the whole expression after the O in display equation 1 in parentheses.

In reply to Re: Can you improve upon my algorithm. by bitingduck
in thread Can you improve upon my algorithm. by BrowserUk

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.