- base = (char *)basep; /* set up char * base pointer */
- thresh = T * size; /* init threshold */
- sp = stack; /* init stack pointer */
- limit = base + nelems * size;/* pointer past end of array */
- for ( ;; ) { /* repeat until break... */
- if ( limit - base > thresh ) { /* if more than T elements */
- /* swap base with middle */
- SWAP(((((size_t)(limit-base))/size)/2)*size+base, base);
- i = base + size; /* i scans left to right */
- j = limit - size; /* j scans right to left */
- if ( COMP(i, j) > 0 ) /* Sedgewick's */
- SWAP(i, j); /* three-element sort */
- if ( COMP(base, j) > 0 ) /* sets things up */
- SWAP(base, j); /* so that */
- if ( COMP(i, base) > 0 ) /* *i <= *base <= *j */
- SWAP(i, base); /* *base is pivot element */
- for ( ;; ) { /* loop until break */
- do /* move i right */
- i += size; /* until *i >= pivot */
- while ( COMP(i, base) < 0 );
- do /* move j left */
- j -= size; /* until *j <= pivot */
- while ( COMP(j, base) > 0 );
- if ( i > j ) /* if pointers crossed */
- break; /* break loop */
- SWAP(i, j); /* else swap elements, keep scanning*/
- }
- SWAP(base, j); /* move pivot into correct place */
- if ( j - base > limit - i ) { /* if left subfile larger */
- sp[0] = base; /* stack left subfile base */
- sp[1] = j; /* and limit */
- base = i; /* sort the right subfile */
- } else { /* else right subfile larger*/
- sp[0] = i; /* stack right subfile base */
- sp[1] = limit; /* and limit */
- limit = j; /* sort the left subfile */
- }
- sp += 2; /* increment stack pointer */
- } else { /* else subfile is small, use insertion sort */
- for ( j = base, i = j+size; i < limit; j = i, i += size )
- for ( ; COMP(j, j+size) > 0; j -= size ) {
- SWAP(j, j+size);
- if ( j == base )
- break;
- }
- if ( sp != stack ) { /* if any entries on stack */
- sp -= 2; /* pop the base and limit */
- base = sp[0];
- limit = sp[1];
- } else /* else stack empty, done */
- break;
- }
- }