Weird things when calculating the size for a mergesort-buffer

Discussion in 'C++' started by Gerald Breuer, Apr 1, 2013.

  1. I've got a simple straightforward mergesort implementation and the
    function mergesort calculates the size for the external memory in a
    loop with the result sbSize; the size is calculated in the loop from
    the lines with the comments "here" and "to here".

    template<typename T, typename Pred>
    void mergesort_rc( T *ptElements, T *ptBack, size_t elements,
    Pred &pred, T *ptSortBuffer );

    template<typename T, typename Pred>
    void mergesort( T *ptElements, size_t elements, Pred &pred )
    {
    if( elements > 2 )
    {
    size_t sbSize,
    sbsAdd;
    T *ptSortBuffer;

    sbSize = 0; // here
    sbsAdd = elements;
    do
    sbSize += sbsAdd,
    sbsAdd = sbsAdd - sbsAdd / 2;
    while( sbsAdd > 2 ); // to here

    ptSortBuffer = new T[sbSize];
    mergesort_rc( ptElements, ptElements, elements, pred,
    ptSortBuffer );
    delete[] ptSortBuffer;
    }
    else
    if( elements == 2 )
    swap( ptElements[0], ptElements[1] );
    }

    template<typename T, typename Pred>
    void mergesort_rc( T *ptElements, T *ptBack, size_t elements, Pred
    &pred, T *ptSortBuffer )
    {
    if( elements > 2 )
    {
    size_t leftElements,
    rightElements;
    T *ptLeft,
    *ptRight;
    T *ptNextSortBuffer;

    leftElements = elements / 2;
    rightElements = elements - leftElements;
    ptLeft = ptSortBuffer;
    ptRight = ptSortBuffer + leftElements;
    ptNextSortBuffer = ptRight + rightElements;

    if( leftElements > 1 )
    mergesort_rc( ptElements, ptLeft, leftElements, pred,
    ptNextSortBuffer );
    else
    *ptLeft = *ptElements;

    mergesort_rc( ptElements + leftElements, ptRight, rightElements,
    pred, ptNextSortBuffer );

    for( T *ptLeftEnd = ptRight,
    *ptRightEnd = ptNextSortBuffer; ; )
    if( pred( *ptLeft, *ptRight ) )
    {
    *ptBack++ = *ptLeft;

    if( ++ptLeft == ptLeftEnd )
    return (void)copy_objects( ptRight, ptRightEnd - ptRight,
    ptBack );
    }
    else
    {
    *ptBack++ = *ptRight;

    if( ++ptRight == ptRightEnd )
    return (void)copy_objects( ptLeft, ptLeftEnd - ptLeft,
    ptBack );
    }
    }
    else
    if( pred( ptElements[0], ptElements[1] ) )
    ptBack[0] = ptElements[0],
    ptBack[1] = ptElements[1];
    else
    ptBack[0] = ptElements[1],
    ptBack[1] = ptElements[0];
    }

    So I tried to find out if there is a general formula to calculate the
    size faster. I found that the resulting sbSize is alwas around 2 * ele-
    ments and I thought that if I would add a safe offset to this 2 * ele-
    ments I things would go right. So I looked what's the maximum offset
    necessary while iterating over a certain input-size.

    #include <stdio.h>
    #include <limits.h>

    template<typename UINT_T> // outputs highest set bit
    unsigned hsb( UINT_T ui )
    {
    UINT_T mask;
    unsigned test, bits;

    mask = (UINT_T)-1 << (sizeof(UINT_T) * CHAR_BIT / 2);
    test = sizeof(UINT_T) * CHAR_BIT / 2;
    bits = 0;
    do
    {
    if( ui & mask )
    ui >>= test,
    bits += test;

    test = test / 2;
    mask >>= test;
    } while( test != 0 );

    return bits;
    }

    int main()
    {
    int m = 0;

    for( unsigned e = 1; e <= 0x80000001u; e++ )
    {
    unsigned s, a;
    int d;

    s = 0;
    a = e;
    do
    s += a;
    while( (a = a - a / 2) > 2 );

    if( (d = (int)(s - 2 * e)) > m )
    {
    m = d;
    printf( "max (% 8X): %d, %u\n", e, m, hsb( e ) );
    }
    }

    return 0;
    }

    The program outputs the following:

    max ( 21): 1, 5
    max ( 41): 2, 6
    max ( 81): 3, 7
    max ( 101): 4, 8
    max ( 201): 5, 9
    max ( 401): 6, 10
    max ( 801): 7, 11
    max ( 1001): 8, 12
    max ( 2001): 9, 13
    max ( 4001): 10, 14
    max ( 8001): 11, 15
    max ( 10001): 12, 16
    max ( 20001): 13, 17
    max ( 40001): 14, 18
    max ( 80001): 15, 19
    max ( 100001): 16, 20
    max ( 200001): 17, 21
    max ( 400001): 18, 22
    max ( 800001): 19, 23
    max ( 1000001): 20, 24
    max ( 2000001): 21, 25
    max ( 4000001): 22, 26
    max ( 8000001): 23, 27
    max (10000001): 24, 28
    max (20000001): 25, 29
    max (40000001): 26, 30
    max (80000001): 27, 31

    So when the size is <= 2^5 I'm fine with a sort-buffer 2*e elements.
    From 2^5+1 to 2^6 I I'm fine with a sort-buffer of 2*e+1 and so on.
    What's the matematical reason behind that or is there a more simple
    formula without any linear or logarithmical (counting the bits) ap-
    proach to calculate the sort-buffer-size?
    Gerald Breuer, Apr 1, 2013
    #1
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Raja
    Replies:
    12
    Views:
    24,351
    John Harrison
    Jun 21, 2004
  2. Jamal

    Problems with mergesort for files

    Jamal, Jul 14, 2003, in forum: C Programming
    Replies:
    1
    Views:
    446
    Jamal
    Jul 15, 2003
  3. Jamal
    Replies:
    6
    Views:
    610
    Dann Corbit
    Jul 16, 2003
  4. ben81

    MergeSort

    ben81, Aug 9, 2006, in forum: Python
    Replies:
    1
    Views:
    481
    Steven D'Aprano
    Aug 10, 2006
  5. =?Utf-8?B?V2lsbGlhbSBTdWxsaXZhbg==?=

    vs2005 publish website doing bad things, bad things

    =?Utf-8?B?V2lsbGlhbSBTdWxsaXZhbg==?=, Oct 25, 2006, in forum: ASP .Net
    Replies:
    1
    Views:
    589
    =?Utf-8?B?UGV0ZXIgQnJvbWJlcmcgW0MjIE1WUF0=?=
    Oct 25, 2006
Loading...

Share This Page