[Home]
[Contents]
[Chapter]
[Previous Algorithm]
[Next Algorithm]


Polyphase merge sort


sort() { int i, j, some; extern int maxfiles, maxruns[], actruns[]; extern struct rec LastRec[]; /*** Initialize input/output files ***/ OpenRead( 1 ); for (i=2; i<=maxfiles; i++) OpenWrite( i ); /*** Initialize maximum and actual count of runs ***/ for (i=0; i<=maxfiles; i++) maxruns[i] = actruns[i] = 0; maxruns[0] = maxruns[maxfiles] = 1; distribute(); /*** Initialize merging phase ***/ for (i=2; i<=maxfiles; i++) { OpenRead( i ); LastRec[i] = ReadFile(i); } for (i=1; maxruns[0]>1; i = (i%maxfiles)+1 ) { OpenWrite( i ); while ( maxruns[ (i%maxfiles)+1 ] > 0 ) { for (j=1; j<=maxfiles; j++) if ( j!=i ) { if ( maxruns[j]>actruns[j] ) FilStat[j] = '-'; else { FilStat[j] = 'i'; actruns[j]--; some = TRUE; } maxruns[j]--; maxruns[0]--; } maxruns[i]++; maxruns[0]++; if (some) { merge(i); actruns[i]++; } } OpenRead( i ); LastRec[i] = ReadFile(i); }; return( i==1 ? maxfiles : i-1 ); };

C source (444.sort.c)



© Addison-Wesley Publishing Co. Inc.