24 #define SWAP(a, b) { int c = *(a); *(a) = *(b); *(b) = c; }
34 #define STACK_SIZE (CHAR_BIT * sizeof(size_t))
35 #define PUSH(low, high) ((void) ((top->lo = (low)), (top->hi = (high)), ++top))
36 #define POP(low, high) ((void) (--top, (low = top->lo), (high = top->hi)))
37 #define STACK_NOT_EMPTY (stack < top)
39 #define min(x, y) ((x) < (y) ? (x) : (y))
44 register int *base_ptr = pbase;
46 if(total_elems == 0)
return;
48 if(total_elems > MAX_THRESH)
51 int *hi = lo + total_elems - 1;
57 while (STACK_NOT_EMPTY)
68 int *mid = lo + ((hi - lo) >> 1);
88 while (*left_ptr < *mid)
91 while (*mid < *right_ptr)
94 if(left_ptr < right_ptr)
96 SWAP(left_ptr, right_ptr);
99 else if(mid == right_ptr)
104 else if(left_ptr == right_ptr)
111 while (left_ptr <= right_ptr);
118 if((
size_t) (right_ptr - lo) <= MAX_THRESH)
120 if((
size_t) (hi - left_ptr) <= MAX_THRESH)
127 else if((
size_t) (hi - left_ptr) <= MAX_THRESH)
130 else if((right_ptr - lo) > (hi - left_ptr))
151 int *
const end_ptr = base_ptr + total_elems - 1;
152 int *tmp_ptr = base_ptr;
153 int *thresh = min(end_ptr, base_ptr + MAX_THRESH);
154 register int *run_ptr;
160 for (run_ptr = tmp_ptr + 1; run_ptr <= thresh; run_ptr++)
161 if(*run_ptr < *tmp_ptr)
164 if(tmp_ptr != base_ptr)
165 SWAP(tmp_ptr, base_ptr);
168 run_ptr = base_ptr + 1;
169 while (++run_ptr <= end_ptr)
171 tmp_ptr = run_ptr - 1;
172 while (*run_ptr < *tmp_ptr)
176 if(tmp_ptr != run_ptr)
179 register int *hi, *lo;
181 for (hi = lo = run_ptr; --lo >= tmp_ptr; hi = lo)