Maybe you shouldn=E2=80=99t have renamed the variables. That introduced =
a bug. Here=E2=80=99s the diff:

rceCode diff">-at--at- -34,7 +34,7 -at--at- void track(int* in, int =
left, int right, int* space)
        track(in, pos2, pos3, space);
        for(i =3D 0; i < length; i++)
    {
-       if(pos1 < pos2 && ( pos2 =3D=3D pos3 =
|| max(in[pos1], in[pos2]) =3D=3D in[pos1]))
+       if(pos1 < left+mpt && ( pos2 =3D=3D r=
ight || max(in[pos1], in[pos2]) =3D=3D in[pos1]))
        {
        space[i] =3D in[pos1];
        pos1++;

Indeed, at the starting point, pos2 =3D=3D left+mpt and de>pos3 =3D=3D right, but pos2 and pos3 m>change throughout the merge loop. What you=E2=80=99re comparing them=
to is supposed to stay fixed.

With that change, it works.

(Unclear to me why pos1 and pos2 are more =E2=
=80=9Csensible=E2=80=9D names than l, r but okay=
=E2=80=A6)

I can make further suggestions about logging and about a much better dat=
a structure that actually takes advantage of C++. Instead of managing all t=
his left/right/mid stuff manually, write a small array_slice c=
lass that defines the operator[] to look up in a given array u=
sing an offset. Then you can write a 0-based merge much more cleanly.

CL

Ruben Safir ruben-at-mrbrklyn.com=
writes:

I can=E2=80=99t finish by tonight. I borrowed a mergesort algorithm from=
the net at here

http://www.cprogramming.com/tutorial/computersciencetheory/merge.html

I ported it to C++ and it failed to work. I changed the name of the vars=
to more sensible names, and converged some of his math because what was th=
ere just seemed to sloppy. I mocked it and merged the last subroutine direc=
tly in main and it just failed to work. So I then copied and pasted his wor=
k and altered it to make it a complete c program and it does work :(

I can=E2=80=99t find what I did wrong. I might have just been better off=
writing it by myself but I wanted to finish before class tonight, and to f=
ocus on the thread library.

Its 4PM and I=E2=80=99m out of time. Attached at the cpp files and the c=
files

They are all part of the C++ code accept for the one with the c sufix. T=
hat one is the copy and paste version. This will take another day at least.=

Reuvain

=E2=80=93 So many immigrant groups have swept through our town that Broo=
klyn, like Atlantis, reaches mythological proportions in the mind of the wo=
rld - RI Safir 1998 http://www.mrbrklyn.com

DRM is THEFT - We are the STAKEHOLDERS - RI Safir 2002 http://www.nylxs.=
com - Leadership Development in Free Software http://www2.mrbrklyn.com/reso=
urces - Unpublished Archive http://www.coinhangout.com - coins! http://www.=
brooklyn-living.com

Being so tracked is for FARM ANIMALS and and extermination camps, but in=
compatible with living as a free human being. -RI Safir 2013 / =
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D Filename: main.cpp Des=
cription: merge sort main Version: 1.0 * Created: 11/09/2016 09:=
33:20 AM * Revision: none * Compiler: gcc Author: Dr.=C2=A0Fritz=
Mehner (mn), mehner-at-fh-swf.de * Company: FH S=C3=BCdwestfalen, Iserlohn m> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D */ #include #include =E2=
=80=9Cmsort.h=E2=80=9D #include #include

define SIZE 20

int main(int argv, char **argc) { using namespace std;

int data =3D new int[SIZE]; int cache =3D new int[SIZE]; struct=
timespec now; clock_gettime(CLOCK_REALTIME, &now); long seed =3D now.t=
v_nsec; srand( (unsigned int) seed); for(int i =3D 0; i < SIZE; i++){ da=
ta[i] =3D rand() % 1000; cout << data[i] << =E2=80=9C=E2=80=9D;=
} cout << endl;

cout << =E2=80=9C_________________________________________________=
_______=E2=80=9D << endl;

for(int i =3D 0; i < SIZE; i++){ cout << =E2=80=9CBefore:=E2=80=
=9D << i << " =3D=3D> " << data[i] << =
=E2=80=9C=E2=80=9D << endl; } merge::track(data, 0, SIZE, cache); for=
(int i =3D 0; i < SIZE; i++){ cout << =E2=80=9CAfter:=E2=80=9D <=
;< i << =E2=80=9C=3D=3D>=E2=80=9D << data[i] << =E2=
=80=9C=E2=80=9D << endl; }

return 0;

}

CXX:=3Dg++ CXXFLAGS:=3D-Wall -ggdb

LDFLAGS:=3D-L/usr/local/lib/mysql -lmysqlpp -lmysqlclient

msort : msort.o main.o ${CXX} ${CXXFLAGS} -o msort msort.o main.o

main.o : main.cpp ${CXX} ${CXXFLAGS} -o main.o -c main.cpp

msort.o : msort.cpp msort.h ${CXX} ${CXXFLAGS} -c msort.cpp

clean : rm nodes .o make.deps touch .cpp *.h

include make.deps make.deps: .cpp ; gcc -M .cpp >$-at- #include=
=E2=80=9Cmsort.h=E2=80=9D #include

namespace merge{

int max(int x, int y){ int ret; x>y ? ret=3Dx : ret=3Dy; std::cout &l=
t;< x << =E2=80=9C:=E2=80=9D << y << =E2=80=9C=3D=3D&g=
t;=E2=80=9D << ret << std::endl; return ret; }

void track(int* in, int left, int right, int* space) { int i =3D 0;

if(right =3D=3D left + 1){ std::cout << =E2=80=9CBACKUP=E2=80=9D &=
lt;< std::endl; return; }

int length =3D right - left; std::cout << =E2=80=9Clength =3D>=
=E2=80=9D << length << std::endl; int mpt =3D length/2; std::co=
ut << =E2=80=9Cmpt =3D>=E2=80=9D << mpt << std::endl; =
int pos1 =3D left; int pos2 =3D left + mpt; int pos3 =3D right; std::cout &=
lt;< =E2=80=9Cpos1 =3D>=E2=80=9D << pos1 << " pos2=
=3D=3D>" << pos2 << " pos3=3D=3D>" <<=
; pos3 << std::endl; //do the recursion now on the left and right bra=
nches std::cout << =E2=80=9CLEFT <<=3D=3D=E2=80=9D << std=
::endl; track(in, pos1, pos2, space); std::cout << =E2=80=9CRIGHT =3D=
=3D>>=E2=80=9D << std::endl; track(in, pos2, pos3, space); for(=
i =3D 0; i < length; i++) { if(pos1 < pos2 && ( pos2 =3D=3D p=
os3 || max(in[pos1], in[pos2]) =3D=3D in[pos1])) { space[i] =3D in[pos1]; p=
os1++; } else{ space[i] =3D in[pos2]; pos2++; } } /* transfer array segment=
*/ for(i =3D left; i < right; i++) { in[i] =3D space[i - left]; } }

}//end namespace / =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D =
Filename: msort.h Description: Header File for Parrell Msort alg=
orthm Version: 1.0 * Created: 11/09/2016 04:28:51 AM * Revision:=
none * Compiler: gcc Author: Ruben Safir * Company: NYLXS Inc <=
em> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D */ #ifndef MSORT_INC #define MSO=
RT_INC

namespace merge{

int max(int x, int y); void track(int* , int , int , int* ); //int sort(=
int &input , int size);

} #endif /* =E2=80=94=E2=80=93 #ifndef MSORT_INC =E2=80=94=E2=80=93 */p>

119 480 914 629 352 111 923 92 636 152 286 104 244 432 617 669 367 309 1=
74 474 ________________________________________________________ Before: 0 =
=3D=3D> 119
Before: 1 =3D=3D> 480
Before: 2 =3D=3D> 914<=
br />Before: 3 =3D=3D> 629
Before: 4 =3D=3D> 352
Before: 5 =
=3D=3D> 111
Before: 6 =3D=3D> 923
Before: 7 =3D=3D> 92 B=
efore: 8 =3D=3D> 636
Before: 9 =3D=3D> 152
Before: 10 =3D=
=3D> 286
Before: 11 =3D=3D> 104
Before: 12 =3D=3D> 244r />Before: 13 =3D=3D> 432
Before: 14 =3D=3D> 617
Before: 1=
5 =3D=3D> 669
Before: 16 =3D=3D> 367
Before: 17 =3D=3D> =
309
Before: 18 =3D=3D> 174
Before: 19 =3D=3D> 474
leng=
th =3D>20 mpt =3D>10 pos1 =3D>0 pos2=3D=3D>10 pos3=3D=3D>20 =
LEFT <<=3D=3D length =3D>10 mpt =3D>5 pos1 =3D>0 pos2=3D=3D&=
gt;5 pos3=3D=3D>10 LEFT <<=3D=3D length =3D>5 mpt =3D>2 pos1=
=3D>0 pos2=3D=3D>2 pos3=3D=3D>5 LEFT <<=3D=3D length =3D>=
;2 mpt =3D>1 pos1 =3D>0 pos2=3D=3D>1 pos3=3D=3D>2 LEFT <<=
=3D=3D BACKUP RIGHT =3D=3D>> BACKUP 119:480=3D=3D>480 RIGHT =3D=3D=
>> length =3D>3 mpt =3D>1 pos1 =3D>2 pos2=3D=3D>3 pos3=3D=
=3D>5 LEFT <<=3D=3D BACKUP RIGHT =3D=3D>> length =3D>2 mp=
t =3D>1 pos1 =3D>3 pos2=3D=3D>4 pos3=3D=3D>5 LEFT <<=3D=
=3D BACKUP RIGHT =3D=3D>> BACKUP 629:352=3D=3D>629 914:629=3D=3D&g=
t;914 629:352=3D=3D>629 480:914=3D=3D>914 480:629=3D=3D>629 480:62=
9=3D=3D>629 RIGHT =3D=3D>> length =3D>5 mpt =3D>2 pos1 =3D&g=
t;5 pos2=3D=3D>7 pos3=3D=3D>10 LEFT <<=3D=3D length =3D>2 mp=
t =3D>1 pos1 =3D>5 pos2=3D=3D>6 pos3=3D=3D>7 LEFT <<=3D=
=3D BACKUP RIGHT =3D=3D>> BACKUP 111:923=3D=3D>923 RIGHT =3D=3D>=
;> length =3D>3 mpt =3D>1 pos1 =3D>7 pos2=3D=3D>8 pos3=3D=3D=
>10 LEFT <<=3D=3D BACKUP RIGHT =3D=3D>> length =3D>2 mpt =
=3D>1 pos1 =3D>8 pos2=3D=3D>9 pos3=3D=3D>10 LEFT <<=3D=3D=
BACKUP RIGHT =3D=3D>> BACKUP 636:152=3D=3D>636 92:636=3D=3D>63=
6 92:152=3D=3D>152 923:636=3D=3D>923 111:636=3D=3D>636 111:152=3D=
=3D>152 111:92=3D=3D>111 636:92=3D=3D>636 914:923=3D=3D>923 914=
:636=3D=3D>914 629:636=3D=3D>636 629:152=3D=3D>629 629:152=3D=3D&g=
t;629 480:152=3D=3D>480 119:152=3D=3D>152 119:111=3D=3D>119 923:11=
1=3D=3D>923 636:111=3D=3D>636 RIGHT =3D=3D>> length =3D>10 m=
pt =3D>5 pos1 =3D>10 pos2=3D=3D>15 pos3=3D=3D>20 LEFT <<=
=3D=3D length =3D>5 mpt =3D>2 pos1 =3D>10 pos2=3D=3D>12 pos3=3D=
=3D>15 LEFT <<=3D=3D length =3D>2 mpt =3D>1 pos1 =3D>10 p=
os2=3D=3D>11 pos3=3D=3D>12 LEFT <<=3D=3D BACKUP RIGHT =3D=3D>=
;> BACKUP 286:104=3D=3D>286 RIGHT =3D=3D>> length =3D>3 mpt =
=3D>1 pos1 =3D>12 pos2=3D=3D>13 pos3=3D=3D>15 LEFT <<=3D=
=3D BACKUP RIGHT =3D=3D>> length =3D>2 mpt =3D>1 pos1 =3D>13=
pos2=3D=3D>14 pos3=3D=3D>15 LEFT <<=3D=3D BACKUP RIGHT =3D=3D&=
gt;> BACKUP 432:617=3D=3D>617 244:617=3D=3D>617 244:432=3D=3D>4=
32 286:617=3D=3D>617 286:432=3D=3D>432 286:244=3D=3D>286 104:244=
=3D=3D>244 RIGHT =3D=3D>> length =3D>5 mpt =3D>2 pos1 =3D>=
;15 pos2=3D=3D>17 pos3=3D=3D>20 LEFT <<=3D=3D length =3D>2 m=
pt =3D>1 pos1 =3D>15 pos2=3D=3D>16 pos3=3D=3D>17 LEFT <<=
=3D=3D BACKUP RIGHT =3D=3D>> BACKUP 669:367=3D=3D>669 RIGHT =3D=3D=
>> length =3D>3 mpt =3D>1 pos1 =3D>17 pos2=3D=3D>18 pos3=
=3D=3D>20 LEFT <<=3D=3D BACKUP RIGHT =3D=3D>> length =3D>=
2 mpt =3D>1 pos1 =3D>18 pos2=3D=3D>19 pos3=3D=3D>20 LEFT <&l=
t;=3D=3D BACKUP RIGHT =3D=3D>> BACKUP 174:474=3D=3D>474 309:474=3D=
=3D>474 309:174=3D=3D>309 474:174=3D=3D>474 669:474=3D=3D>669 3=
67:474=3D=3D>474 367:309=3D=3D>367 474:309=3D=3D>474 617:669=3D=3D=
>669 617:474=3D=3D>617 432:474=3D=3D>474 432:367=3D=3D>432 286:=
367=3D=3D>367 286:474=3D=3D>474 286:309=3D=3D>309 923:669=3D=3D>=
;923 914:669=3D=3D>914 636:669=3D=3D>669 636:617=3D=3D>636 629:617=
=3D=3D>629 629:617=3D=3D>629 480:617=3D=3D>617 480:474=3D=3D>48=
0 152:474=3D=3D>474 152:432=3D=3D>432 152:367=3D=3D>367 152:474=3D=
=3D>474 152:309=3D=3D>309 152:286=3D=3D>286 152:244=3D=3D>244 1=
52:104=3D=3D>152 119:104=3D=3D>119 923:104=3D=3D>923 636:104=3D=3D=
>636 669:104=3D=3D>669 After: 0=3D=3D> 923
After: 1=3D=3D>=
914
After: 2=3D=3D> 669
After: 3=3D=3D> 636
After: 4=
=3D=3D> 629
After: 5=3D=3D> 629
After: 6=3D=3D> 617
>After: 7=3D=3D> 480
After: 8=3D=3D> 474
After: 9=3D=3D>=
432
After: 10=3D=3D> 367
After: 11=3D=3D> 474
After: =
12=3D=3D> 309
After: 13=3D=3D> 286
After: 14=3D=3D> 244<=
br />After: 15=3D=3D> 152
After: 16=3D=3D> 119
After: 17=3D=
=3D> 923
After: 18=3D=3D> 636
After: 19=3D=3D> 669
=
#include =E2=80=9Cstdlib.h=E2=80=9D #include =E2=80=9Ctime.h=E2=80=9D #incl=
ude =E2=80=9Cstdio.h=E2=80=9D

define SIZE 500

/* Helper function for finding the max of two numbers */ int max(int x, =
int y) { if(x > y) { return x; } else { return y; } }

/* left is the index of the leftmost element of the subarray; right is o=
ne * past the index of the rightmost element / void merge_helper(int em>input, int left, int right, int scratch) { / base case: one ele=
ment / if(right =3D=3D left + 1) { return; } else { int i =3D 0; int le=
ngth =3D right - left; int midpoint_distance =3D length/2; / l and r a=
re to the positions in the left and right subarrays */ int l =3D left, r =
=3D left + midpoint_distance;

    /* sort each subarray */
    merge_helper(input, left, left + midpoint_distance, scratch);
    merge_helper(input, left + midpoint_distance, right, scratch);

    /* merge the arrays together using scratch for temporary storage */=20
    for(i =3D 0; i < length; i++)
    {
        /* Check to see if any elements remain in the left array; if so,
         * we check if there are any elements left in the right array; if
         * so, we compare them.  Otherwise, we know that the merge must
         * use take the element from the left array */
        if(l < left + midpoint_distance &&=20
                (r =3D=3D right || max(input[l], input[r]) =3D=3D input[l]))
        {
            scratch[i] =3D input[l];
            l++;
        }
        else
        {
            scratch[i] =3D input[r];
            r++;
        }
    }
    /* Copy the sorted subarray back to the input */
    for(i =3D left; i < right; i++)
    {
        input[i] =3D scratch[i - left];
    }
}

}

/* mergesort returns true on success. Note that in C++, you could also *=
replace malloc with new and if memory allocation fails, an exception will =
* be thrown. If we don=E2=80=99t allocate a scratch array here, what happen=
s? Elements are sorted in reverse order =E2=80=93 greatest to le=
ast */

int mergesort(int input, int size) { int scratch =3D (int )=
malloc(size sizeof(int)); if(scratch !=3D NULL) { merge_helper(input,=
0, size, scratch); free(scratch); return 1; } else { return 0; } }

int main(int argc, char** argv) { int data =3D (int )malloc(SIZ=
E * sizeof(int )); struct timespec now; clock_gettime(CLOCK_REALTIME, &=
now); long seed =3D now.tv_nsec; srand( (unsigned int) seed); for(int i =3D=
0; i < SIZE; i++){ data[i] =3D rand() % 1000; printf(=E2=80=9C%i =E2=80=
=9D, data[i] ); } printf(=E2=80=9C=E2=80=9D);

printf (=E2=80=9C_______________________________________________________=
_=E2=80=9D); mergesort(data, SIZE); for(int i =3D 0; i < SIZE; i++){ pri=
ntf(=E2=80=9C%i =E2=80=9D, data[i] ); } printf(=E2=80=9C=E2=80=9D); return =
0; }

---

Learn mailing list Learn-at-nylxs.com http://lists.mrbrklyn.com/mailman/lis=
tinfo/learn