Lines Matching defs:runs
63 ** initialize looking for natural runs, we'll always produce stable
127 ** The array of elements at list1 will be organized into runs of length 2,
128 ** or runs of length >= 2 * PTHRESH. We only try to form long runs when
136 ** p2 parallels b in the list2 array, where runs are defined by
180 IV runs = 0;
193 /* Having laid out the playing field, look for long runs */
219 p2 = NEXT(p2) = p2 + (p - b); ++runs;
229 p2 = NEXT(p2) = p2 + 2; ++runs;
237 NEXT(p2) = p2 + 1; ++runs;
244 return runs;
260 * Suppose we have five runs (each typically of length 2 after dynprep).
270 * This means, on pass 1, the records in runs 1 and 2 aren't revisited until
271 * runs 3 and 4 are merged and the runs from run 5 have been copied.
278 * # merge $runs runs at offset $offset of list $list1 into $list2.
279 * # all unmerged runs ($runs == 1) originate in list $base.
281 * my ($offset, $runs, $base, $list1, $list2) = @_;
283 * if ($runs == 1) {
287 * $off2 = mgsort2($offset, $runs-($runs/2), $base, $list2, $list1)
288 * mgsort2($off2, $runs/2, $base, $list2, $list1)
289 * merge the adjacent runs at $offset of $list1 into $list2
290 * return the offset of the end of the merged runs
293 * mgsort2(0, $runs, $base, $aux, $base);
295 * For our 5 runs, the tree of calls looks like
306 * copy runs 1 and 2 from base to aux
307 * merge runs 1 and 2 from aux to base
309 * merge runs 12 and 3 from base to aux
310 * (runs 4 and 5 are where they belong, no copy needed)
311 * merge runs 4 and 5 from base to aux
312 * merge runs 123 and 45 from aux to base
314 * Note that we merge runs 1 and 2 immediately after copying them,
319 * than the original mergesort implementation (only runs 1 and 2 are copied)
320 * and the "balancing" of merges is better (merged runs comprise more nearly
321 * equal numbers of original runs).
324 * to avoid recursion, and will unroll processing of runs of length 2,
329 IV offset; /* offset of 1st of 2 runs at this level */
330 IV runs; /* how many runs must be combined into 1 */
354 stackp->runs = dynprep(aTHX_ base, aux, nmemb, cmp);
359 /* On levels where both runs have be constructed (stackp->runs == 0),
362 * as long as stackp->runs is 0, keep merging.
364 IV runs = stackp->runs;
365 if (runs == 0) {
368 list1 = which[iwhich]; /* area where runs are now */
369 list2 = which[++iwhich]; /* area for merged runs */
377 t = NEXT(t); /* where second runs ends */
469 } while ((runs = stackp->runs) == 0);
473 stackp->runs = 0; /* current run will finish level */
474 /* While there are more than 2 runs remaining,
475 * turn them into exactly 2 runs (at the "other" level),
476 * each made up of approximately half the runs.
480 while (runs > 2) {
484 runs -= stackp->runs = runs / 2;
486 /* We must construct a single run from 1 or 2 runs.
487 * All the original runs are in which[0] == base.
491 if (runs == 1) {
510 /* Constructing a single run from two runs.
512 * We need only make sure the two runs are in the "other" array,
518 stackp->runs = 0; /* take care of both runs, trigger merge */
519 if (!iwhich) { /* Merged runs belong in aux, copy 1st */
527 FROMTOUPTO(f1, f2, t); /* copy both runs */