1N/A * Copyright (C) 1991, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 1N/A * 2000, 2001, 2002, 2003, 2004, by Larry Wall and others 1N/A * You may distribute under the terms of either the GNU General Public 1N/A * License or the Artistic License, as specified in the README file. 1N/A * ...they shuffled back towards the rear of the line. 'No, not at the 1N/A * rear!' the slave-driver shouted. 'Three files up. And stay there... 1N/A/* looks like 'small' is reserved word for WINCE (or somesuch)*/ 1N/A * The mergesort implementation is by Peter M. Mcilroy <pmcilroy@lucent.com>. 1N/A * The original code was written in conjunction with BSD Computer Software 1N/A * Research Group at University of California, Berkeley. 1N/A * See also: "Optimistic Merge Sort" (SODA '92) 1N/A * The integration to Perl is by John P. Linderman <jpl@research.att.com>. 1N/A * The code can be distributed under the same terms as Perl itself. 1N/Atypedef char *
aptr;
/* pointer for arithmetic on sizes */ 1N/Atypedef SV *
gptr;
/* pointers in our lists */ 1N/A/* Binary merge internal sort, with a few special mods 1N/A** for the special perl environment it now finds itself in. 1N/A** Things that were once options have been hotwired 1N/A** to values suitable for this use. In particular, we'll always 1N/A** initialize looking for natural runs, we'll always produce stable 1N/A** output, and we'll always do Peter McIlroy's binary merge. 1N/A/* Pointer types for arithmetic and storage and convenience casts */ 1N/A/* byte offset from pointer P to (larger) pointer Q */ 1N/A/* If PSIZE is power of 2, make PSHIFT that power, if that helps */ 1N/A/* Leave optimization to compiler */ 1N/A/* Pointer into other corresponding to pointer into this */ 1N/A/* Runs are identified by a pointer in the auxilliary list. 1N/A** The pointer is at the start of the list, 1N/A** and it points to the start of the next list. 1N/A** NEXT is used as an lvalue, too. 1N/A/* PTHRESH is the minimum number of pairs with the same sense to justify 1N/A** checking for a run and extending it. Note that PTHRESH counts PAIRS, 1N/A** not just elements, so PTHRESH == 8 means a run of 16. 1N/A/* RTHRESH is the number of elements in a run that must compare low 1N/A** to the low element from the opposing run before we justify 1N/A** doing a binary rampup instead of single stepping. 1N/A** In random input, N in a row low should only happen with 1N/A** probability 2^(1-N), so we can risk that we are dealing 1N/A** with orderly input without paying much when we aren't. 1N/A** Overview of algorithm and variables. 1N/A** The array of elements at list1 will be organized into runs of length 2, 1N/A** or runs of length >= 2 * PTHRESH. We only try to form long runs when 1N/A** PTHRESH adjacent pairs compare in the same way, suggesting overall order. 1N/A** Unless otherwise specified, pair pointers address the first of two elements. 1N/A** b and b+1 are a pair that compare with sense ``sense''. 1N/A** b is the ``bottom'' of adjacent pairs that might form a longer run. 1N/A** p2 parallels b in the list2 array, where runs are defined by 1N/A** t represents the ``top'' of the adjacent pairs that might extend 1N/A** the run beginning at b. Usually, t addresses a pair 1N/A** that compares with opposite sense from (b,b+1). 1N/A** However, it may also address a singleton element at the end of list1, 1N/A** or it may be equal to ``last'', the first element beyond list1. 1N/A** r addresses the Nth pair following b. If this would be beyond t, 1N/A** we back it off to t. Only when r is less than t do we consider the 1N/A** run long enough to consider checking. 1N/A** q addresses a pair such that the pairs at b through q already form a run. 1N/A** Often, q will equal b, indicating we only are sure of the pair itself. 1N/A** However, a search on the previous cycle may have revealed a longer run, 1N/A** so q may be greater than b. 1N/A** p is used to work back from a candidate r, trying to reach q, 1N/A** which would mean b through r would be a run. If we discover such a run, 1N/A** we start q at r and try to push it further towards t. 1N/A** If b through r is NOT a run, we detect the wrong order at (p-1,p). 1N/A** In any event, after the check (if any), we have two main cases. 1N/A** 1) Short run. b <= q < p <= r <= t. 1N/A** b through q is a run (perhaps trivial) 1N/A** q through p are uninteresting pairs 1N/A** p through r is a run 1N/A** 2) Long run. b < r <= q < t. 1N/A** b through q is a run (of length >= 2 * PTHRESH) 1N/A** Note that degenerate cases are not only possible, but likely. 1N/A** For example, if the pair following b compares with opposite sense, 1N/A** then b == q < p == r == t. 1N/A /* We just started, or just reversed sense. 1N/A ** Set t at end of pairs with the prevailing sense. 1N/A for (p = b+
2, t = p; ++p <
last; t = ++p) {
1N/A /* Having laid out the playing field, look for long runs */ 1N/A if (r >= t) p = r = t;
/* too short to care about */ 1N/A /* b through r is a (long) run. 1N/A ** Extend it as far as possible. 1N/A while (((p +=
2) < t) &&
1N/A r = p = q +
2;
/* no simple pairs, no after-run */ 1N/A if (q > b) {
/* run of greater than 2 at b */ 1N/A /* pick up singleton, if possible */ 1N/A while (q < p) {
/* simple pairs */ 1N/A if (((b = p) == t) && ((t+
1) ==
last)) {
1N/A/* The original merge sort, in use since 5.7, was as fast as, or faster than, 1N/A * qsort on many platforms, but slower than qsort, conspicuously so, 1N/A * on others. The most likely explanation was platform-specific 1N/A * differences in cache sizes and relative speeds. 1N/A * The quicksort divide-and-conquer algorithm guarantees that, as the 1N/A * problem is subdivided into smaller and smaller parts, the parts 1N/A * fit into smaller (and faster) caches. So it doesn't matter how 1N/A * many levels of cache exist, quicksort will "find" them, and, 1N/A * as long as smaller is faster, take advanatge of them. 1N/A * By contrast, consider how the original mergesort algorithm worked. 1N/A * Suppose we have five runs (each typically of length 2 after dynprep). 1N/A * Adjacent pairs are merged in "grand sweeps" through the input. 1N/A * This means, on pass 1, the records in runs 1 and 2 aren't revisited until 1N/A * runs 3 and 4 are merged and the runs from run 5 have been copied. 1N/A * The only cache that matters is one large enough to hold *all* the input. 1N/A * On some platforms, this may be many times slower than smaller caches. 1N/A * The following pseudo-code uses the same basic merge algorithm, 1N/A * but in a divide-and-conquer way. 1N/A * # merge $runs runs at offset $offset of list $list1 into $list2. 1N/A * # all unmerged runs ($runs == 1) originate in list $base. 1N/A * my ($offset, $runs, $base, $list1, $list2) = @_; 1N/A * if ($list1 is $base) copy run to $list2 1N/A * return offset of end of list (or copy) 1N/A * $off2 = mgsort2($offset, $runs-($runs/2), $base, $list2, $list1) 1N/A * mgsort2($off2, $runs/2, $base, $list2, $list1) 1N/A * merge the adjacent runs at $offset of $list1 into $list2 1N/A * return the offset of the end of the merged runs 1N/A * mgsort2(0, $runs, $base, $aux, $base); 1N/A * For our 5 runs, the tree of calls looks like 1N/A * and the corresponding activity looks like 1N/A * copy runs 1 and 2 from base to aux 1N/A * merge runs 1 and 2 from aux to base 1N/A * (run 3 is where it belongs, no copy needed) 1N/A * merge runs 12 and 3 from base to aux 1N/A * (runs 4 and 5 are where they belong, no copy needed) 1N/A * merge runs 4 and 5 from base to aux 1N/A * merge runs 123 and 45 from aux to base 1N/A * Note that we merge runs 1 and 2 immediately after copying them, 1N/A * while they are still likely to be in fast cache. Similarly, 1N/A * run 3 is merged with run 12 while it still may be lingering in cache. 1N/A * This implementation should therefore enjoy much of the cache-friendly 1N/A * behavior that quicksort does. In addition, it does less copying 1N/A * than the original mergesort implementation (only runs 1 and 2 are copied) 1N/A * and the "balancing" of merges is better (merged runs comprise more nearly 1N/A * equal numbers of original runs). 1N/A * The actual cache-friendly implementation will use a pseudo-stack 1N/A * to avoid recursion, and will unroll processing of runs of length 2, 1N/A * but it is otherwise similar to the recursive implementation. 1N/A IV runs;
/* how many runs must be combined into 1 */ 1N/A if (
nmemb <=
1)
return;
/* sorted trivially */ 1N/A /* On levels where both runs have be constructed (stackp->runs == 0), 1N/A * merge them, and note the offset of their end, in case the offset 1N/A * is needed at the next level up. Hop up a level, and, 1N/A * as long as stackp->runs is 0, keep merging. 1N/A t =
NEXT(p);
/* where first run ends */ 1N/A t =
NEXT(t);
/* where second runs ends */ 1N/A /* If head 1 is larger than head 2, find ALL the elements 1N/A ** in list 2 strictly less than head1, write them all, 1N/A ** then head 1. Then compare the new heads, and repeat, 1N/A ** until one or both lists are exhausted. 1N/A ** In all comparisons (after establishing 1N/A ** which head to merge) the item to merge 1N/A ** (at pointer q) is the first operand of 1N/A ** the comparison. When we want to know 1N/A ** if ``q is strictly less than the other'', 1N/A ** cmp(q, other) < 0 1N/A ** because stability demands that we treat equality 1N/A ** as high when q comes from l2, and as low when 1N/A ** q was from l1. So we ask the question by doing 1N/A ** cmp(q, other) <= sense 1N/A ** and make sense == 0 when equality should look low, 1N/A ** and -1 when equality should look high. 1N/A ** Leave t at something strictly 1N/A ** greater than q (or at the end of the list), 1N/A ** and b at something strictly less than q. 1N/A /* q is known to follow b and must be inserted before t. 1N/A ** Increment b, so the range of possibilities is [b,t). 1N/A ** Round binary split down, to favor early appearance. 1N/A ** Adjust b and t until q belongs just before t. 1N/A /* Copy all the strictly low elements */ 1N/A /* Run out remaining list */ 1N/A /* While there are more than 2 runs remaining, 1N/A * turn them into exactly 2 runs (at the "other" level), 1N/A * each made up of approximately half the runs. 1N/A * Stack the second half for later processing, 1N/A * and set about producing the first half now. 1N/A /* We must construct a single run from 1 or 2 runs. 1N/A * All the original runs are in which[0] == base. 1N/A * The run we construct must end up in which[level&1]. 1N/A /* Constructing a single run from a single run. 1N/A * If it's where it belongs already, there's nothing to do. 1N/A * Otherwise, copy it to where it belongs. 1N/A * A run of 1 is either a singleton at level 0, 1N/A * or the second half of a split 3. In neither event 1N/A * is it necessary to set offset. It will be set by the merge 1N/A * that immediately follows. 1N/A if (
iwhich) {
/* Belongs in aux, currently in base */ 1N/A NEXT(b) = t;
/* set up parallel pointer */ 1N/A }
else if (
level == 0)
goto done;
/* single run at level 0 */ 1N/A /* Constructing a single run from two runs. 1N/A * The merge code at the top will do that. 1N/A * We need only make sure the two runs are in the "other" array, 1N/A * so they'll end up in the correct array after the merge. 1N/A if (!
iwhich) {
/* Merged runs belong in aux, copy 1st */ 1N/A t =
NEXT(t);
/* where second run will end */ 1N/A NEXT(b) = p;
/* paralled pointer for 1st */ 1N/A NEXT(p) = t;
/* ... and for second */ 1N/A * The quicksort implementation was derived from source code contributed 1N/A * NOTE: this code was derived from Tom Horsley's qsort replacement 1N/A * and should not be confused with the original code. 1N/A/* Copyright (C) Tom Horsley, 1997. All rights reserved. 1N/A Permission granted to distribute under the same terms as perl which are 1N/A This program is free software; you can redistribute it and/or modify 1N/A it under the terms of either: 1N/A a) the GNU General Public License as published by the Free 1N/A Software Foundation; either version 1, or (at your option) any 1N/A b) the "Artistic License" which comes with this Kit. 1N/A Details on the perl license can be found in the perl source code which 1N/A This is the most wonderfulest possible qsort I can come up with (and 1N/A still be mostly portable) My (limited) tests indicate it consistently 1N/A does about 20% fewer calls to compare than does the qsort in the Visual 1N/A C++ library, other vendors may vary. 1N/A Some of the ideas in here can be found in "Algorithms" by Sedgewick, 1N/A others I invented myself (or more likely re-invented since they seemed 1N/A pretty obvious once I watched the algorithm operate for a while). 1N/A Most of this code was written while watching the Marlins sweep the Giants 1N/A in the 1997 National League Playoffs - no Braves fans allowed to use this 1N/A code (just kidding :-). 1N/A I realize that if I wanted to be true to the perl tradition, the only 1N/A comment in this file would be something like: 1N/A ...they shuffled back towards the rear of the line. 'No, not at the 1N/A rear!' the slave-driver shouted. 'Three files up. And stay there... 1N/A However, I really needed to violate that tradition just so I could keep 1N/A track of what happens myself, not to mention some poor fool trying to 1N/A understand this years from now :-). 1N/A/* ********************************************************** Configuration */ 1N/A/* QSORT_MAX_STACK is the largest number of partitions that can be stacked up for 1N/A future processing - a good max upper bound is log base 2 of memory size 1N/A (32 on 32 bit machines, 64 on 64 bit machines, etc). In reality can 1N/A safely be smaller than that since the program is taking up some space and 1N/A most operating systems only let you grab some subset of contiguous 1N/A memory (not to mention that you are normally sorting data larger than 1N/A 1 byte element size :-). 1N/A/* QSORT_BREAK_EVEN is the size of the largest partition we should insertion sort. 1N/A Anything bigger and we use qsort. If you make this too small, the qsort 1N/A will probably break (or become less efficient), because it doesn't expect 1N/A the middle element of a partition to be the same as the right or left - 1N/A you have been warned). 1N/A/* QSORT_PLAY_SAFE is the size of the largest partition we're willing 1N/A to go quadratic on. We innoculate larger partitions against 1N/A quadratic behavior by shuffling them before sorting. This is not 1N/A an absolute guarantee of non-quadratic behavior, but it would take 1N/A staggeringly bad luck to pick extreme elements as the pivot 1N/A from randomized data. 1N/A/* ************************************************************* Data Types */ 1N/A/* hold left and right index values of a partition waiting to be sorted (the 1N/A partition includes both left and right - right is NOT one past the end or 1N/A anything like that). 1N/A/* ******************************************************* Shorthand Macros */ 1N/A/* Note that these macros will be used from inside the qsort function where 1N/A we happen to know that the variable 'elt_size' contains the size of an 1N/A array element and the variable 'temp' points to enough space to hold a 1N/A temp element and the variable 'array' points to the array being sorted 1N/A and 'compare' is the pointer to the compare routine. 1N/A Also note that there are very many highly architecture specific ways 1N/A these might be sped up, but this is simply the most generally portable 1N/A code I could think of. 1N/A/* Return < 0 == 0 or > 0 as the value of elt1 is < elt2, == elt2, > elt2 1N/A/* swaps contents of array elements elt1, elt2. 1N/A/* rotate contents of elt1, elt2, elt3 such that elt1 gets elt2, elt2 gets 1N/A elt3 and elt3 gets elt1. 1N/A/* ************************************************************ Debug stuff */ 1N/A return;
/* good place to set a breakpoint */ 1N/A/* ****************************************************************** qsort */ 1N/ASTATIC void /* the standard unstable (u) quicksort (qsort) */ 1N/A /* Make sure we actually have work to do. 1N/A /* Innoculate large partitions against quadratic behavior */ 1N/A /* Setup the initial partition definition and fall into the sorting loop 1N/A /* OK, this is gonna get hairy, so lets try to document all the 1N/A concepts and abbreviations and variables and what they keep 1N/A pc: pivot chunk - the set of array elements we accumulate in the 1N/A middle of the partition, all equal in value to the original 1N/A pivot element selected. The pc is defined by: 1N/A pc_left - the leftmost array index of the pc 1N/A pc_right - the rightmost array index of the pc 1N/A we start with pc_left == pc_right and only one element 1N/A in the pivot chunk (but it can grow during the scan). 1N/A u: uncompared elements - the set of elements in the partition 1N/A we have not yet compared to the pivot value. There are two 1N/A uncompared sets during the scan - one to the left of the pc 1N/A and one to the right. 1N/A u_right - the rightmost index of the left side's uncompared set 1N/A u_left - the leftmost index of the right side's uncompared set 1N/A The leftmost index of the left sides's uncompared set 1N/A doesn't need its own variable because it is always defined 1N/A by the leftmost edge of the whole partition (part_left). The 1N/A same goes for the rightmost edge of the right partition 1N/A We know there are no uncompared elements on the left once we 1N/A get u_right < part_left and no uncompared elements on the 1N/A right once u_left > part_right. When both these conditions 1N/A are met, we have completed the scan of the partition. 1N/A Any elements which are between the pivot chunk and the 1N/A uncompared elements should be less than the pivot value on 1N/A the left side and greater than the pivot value on the right 1N/A side (in fact, the goal of the whole algorithm is to arrange 1N/A for that to be true and make the groups of less-than and 1N/A greater-then elements into new partitions to sort again). 1N/A As you marvel at the complexity of the code and wonder why it 1N/A has to be so confusing. Consider some of the things this level 1N/A of confusion brings: 1N/A Once I do a compare, I squeeze every ounce of juice out of it. I 1N/A never do compare calls I don't have to do, and I certainly never 1N/A I also never swap any elements unless I can prove there is a 1N/A good reason. Many sort algorithms will swap a known value with 1N/A an uncompared value just to get things in the right place (or 1N/A avoid complexity :-), but that uncompared value, once it gets 1N/A compared, may then have to be swapped again. A lot of the 1N/A complexity of this code is due to the fact that it never swaps 1N/A anything except compared values, and it only swaps them when the 1N/A compare shows they are out of position. 1N/A /* Qsort works best when the pivot value is also the median value 1N/A in the partition (unfortunately you can't find the median value 1N/A without first sorting :-), so to give the algorithm a helping 1N/A hand, we pick 3 elements and sort them and use the median value 1N/A of that tiny set as the pivot value. 1N/A Some versions of qsort like to use the left middle and right as 1N/A the 3 elements to sort so they can insure the ends of the 1N/A partition will contain values which will stop the scan in the 1N/A compare loop, but when you have to call an arbitrarily complex 1N/A routine to do a compare, its really better to just keep track of 1N/A array index values to know when you hit the edge of the 1N/A partition and avoid the extra compare. An even better reason to 1N/A avoid using a compare call is the fact that you can drop off the 1N/A edge of the array if someone foolishly provides you with an 1N/A unstable compare function that doesn't always provide consistent 1N/A So, since it is simpler for us to compare the three adjacent 1N/A elements in the middle of the partition, those are the ones we 1N/A pick here (conveniently pointed at by u_right, pc_left, and 1N/A u_left). The values of the left, center, and right elements 1N/A are refered to as l c and r in the following comments. 1N/A /* if l < c, c < r - already in order - nothing to do */ 1N/A /* l < c, c == r - already in order, pc grows */ 1N/A /* l < c, c > r - need to know more */ 1N/A /* l < c, c > r, l < r - swap c & r to get ordered */ 1N/A }
else if (s == 0) {
1N/A /* l < c, c > r, l == r - swap c&r, grow pc */ 1N/A /* l < c, c > r, l > r - make lcr into rlc to get ordered */ 1N/A }
else if (s == 0) {
1N/A /* l == c, c < r - already in order, grow pc */ 1N/A }
else if (s == 0) {
1N/A /* l == c, c == r - already in order, grow pc both ways */ 1N/A /* l == c, c > r - swap l & r, grow pc */ 1N/A /* l > c, c < r - need to know more */ 1N/A /* l > c, c < r, l < r - swap l & c to get ordered */ 1N/A }
else if (s == 0) {
1N/A /* l > c, c < r, l == r - swap l & c, grow pc */ 1N/A /* l > c, c < r, l > r - rotate lcr into crl to order */ 1N/A }
else if (s == 0) {
1N/A /* l > c, c == r - swap ends, grow pc */ 1N/A /* l > c, c > r - swap ends to get in order */ 1N/A /* We now know the 3 middle elements have been compared and 1N/A arranged in the desired order, so we can shrink the uncompared 1N/A /* The above massive nested if was the simple part :-). We now have 1N/A the middle 3 elements ordered and we need to scan through the 1N/A uncompared sets on either side, swapping elements that are on 1N/A the wrong side or simply shuffling equal elements around to get 1N/A all equal elements into the pivot chunk. 1N/A /* Scan the uncompared values on the left. If I find a value 1N/A equal to the pivot value, move it over so it is adjacent to 1N/A the pivot chunk and expand the pivot chunk. If I find a value 1N/A less than the pivot value, then just leave it - its already 1N/A on the correct side of the partition. If I find a greater 1N/A value, then stop the scan. 1N/A }
else if (s == 0) {
1N/A /* Do a mirror image scan of uncompared values on the right 1N/A }
else if (s == 0) {
1N/A /* I know I have a value on the left side which needs to be 1N/A on the right side, but I need to know more to decide 1N/A exactly the best thing to do with it. 1N/A /* I know I have values on both side which are out of 1N/A position. This is a big win because I kill two birds 1N/A with one swap (so to speak). I can advance the 1N/A uncompared pointers on both sides after swapping both 1N/A of them into the right place. 1N/A /* I have an out of position value on the left, but the 1N/A right is fully scanned, so I "slide" the pivot chunk 1N/A and any less-than values left one to make room for the 1N/A greater value over on the right. If the out of position 1N/A value is immediately adjacent to the pivot chunk (there 1N/A are no less-than values), I can do that with a swap, 1N/A otherwise, I have to rotate one of the less than values 1N/A into the former position of the out of position value 1N/A and the right end of the pivot chunk into the left end 1N/A /* Mirror image of complex case above: I have an out of 1N/A position value on the right, but the left is fully 1N/A scanned, so I need to shuffle things around to make room 1N/A for the right value on the left. 1N/A /* No more scanning required on either side of partition, 1N/A break out of loop and figure out next set of partitions 1N/A /* The elements in the pivot chunk are now in the right place. They 1N/A will never move or be compared again. All I have to do is decide 1N/A what to do with the stuff to the left and right of the pivot 1N/A Notes on the QSORT_ORDER_GUESS ifdef code: 1N/A 1. If I just built these partitions without swapping any (or 1N/A very many) elements, there is a chance that the elements are 1N/A already ordered properly (being properly ordered will 1N/A certainly result in no swapping, but the converse can't be 1N/A 2. A (properly written) insertion sort will run faster on 1N/A already ordered data than qsort will. 1N/A 3. Perhaps there is some way to make a good guess about 1N/A switching to an insertion sort earlier than partition size 6 1N/A (for instance - we could save the partition size on the stack 1N/A and increase the size each time we find we didn't swap, thus 1N/A switching to insertion sort earlier for partitions with a 1N/A history of not swapping). 1N/A 4. Naturally, if I just switch right away, it will make 1N/A artificial benchmarks with pure ascending (or descending) 1N/A data look really good, but is that a good reason in general? 1N/A /* There are elements on the left which need more processing. 1N/A Check the right as well before deciding what to do. 1N/A /* We have two partitions to be sorted. Stack the biggest one 1N/A and process the smallest one on the next iteration. This 1N/A minimizes the stack height by insuring that any additional 1N/A stack entries must come from the smallest partition which 1N/A (because it is smallest) will have the fewest 1N/A opportunities to generate additional stack entries. 1N/A /* stack the right partition, process the left */ 1N/A /* stack the left partition, process the right */ 1N/A /* The elements on the left are the only remaining elements 1N/A that need sorting, arrange for them to be processed as the 1N/A /* There is only one chunk on the right to be sorted, make it 1N/A the new partition and loop back around. 1N/A /* This whole partition wound up in the pivot chunk, so 1N/A we need to get a new partition off the stack. 1N/A /* the stack is empty - we are done */ 1N/A /* This partition is too small to fool with qsort complexity, just 1N/A do an ordinary insertion sort to minimize overhead. 1N/A /* Assume 1st element is in right place already, and start checking 1N/A at 2nd element to see where it should be inserted. 1N/A /* Scan (backwards - just in case 'i' is already in right place) 1N/A through the elements already sorted to see if the ith element 1N/A belongs ahead of one of them. 1N/A /* i belongs right after j 1N/A /* Looks like we really need to move some things 1N/A for (k = i -
1; k >= j; --k)
1N/A /* That partition is now sorted, grab the next one, or get out 1N/A of the loop if there aren't any more. 1N/A /* the stack is empty - we are done */ 1N/A /* Believe it or not, the array is sorted at this point! */ 1N/A/* Stabilize what is, presumably, an otherwise unstable sort method. 1N/A * We do that by allocating (or having on hand) an array of pointers 1N/A * that is the same size as the original array of elements to be sorted. 1N/A * We initialize this parallel array with the addresses of the original 1N/A * array elements. This indirection can make you crazy. 1N/A * Some pictures can help. After initializing, we have 1N/A * | | --------------> | | ------> first element to be sorted 1N/A * | | --------------> | | ------> second element to be sorted 1N/A * | | --------------> | | ------> third element to be sorted 1N/A * | | --------------> | | ------> n-1st element to be sorted 1N/A * | | --------------> | | ------> n-th element to be sorted 1N/A * During the sort phase, we leave the elements of list1 where they are, 1N/A * and sort the pointers in the indirect array in the same order determined 1N/A * by the original comparison routine on the elements pointed to. 1N/A * Because we don't move the elements of list1 around through 1N/A * this phase, we can break ties on elements that compare equal 1N/A * using their address in the list1 array, ensuring stabilty. 1N/A * This leaves us with something looking like 1N/A * | | --+ +---> | | ------> first element to be sorted 1N/A * | | --|-------|---> | | ------> second element to be sorted 1N/A * | | --|-------+ +-> | | ------> third element to be sorted 1N/A * +----+ | | | | +----+ 1N/A * | | ---|-+ | +--> | | ------> n-1st element to be sorted 1N/A * | | ---+ +----> | | ------> n-th element to be sorted 1N/A * where the i-th element of the indirect array points to the element 1N/A * that should be i-th in the sorted array. After the sort phase, 1N/A * we have to put the elements of list1 into the places 1N/A * dictated by the indirect array. 1N/A if (
nmemb <=
1)
return;
/* sorted trivially */ 1N/A /* Small arrays can use the stack, big ones must be allocated */ 1N/A /* Copy pointers to original array elements into indirect array */ 1N/A /* sort, with indirection */ 1N/A /* Assert A: all elements of q with index > n are already 1N/A * in place. This is vacuosly true at the start, and we 1N/A * put element n where it belongs below (if it wasn't 1N/A * already where it belonged). Assert B: we only move 1N/A * elements that aren't where they belong, 1N/A * so, by A, we never tamper with elements above n. 1N/A j =
pp[n] - q;
/* This sets j so that q[j] is 1N/A * at pp[n]. *pp[j] belongs in 1N/A * q[j], by construction. 1N/A if (n != j) {
/* all's well if n == j */ 1N/A tmp = q[j];
/* save what's in q[j] */ 1N/A q[j] = *
pp[j];
/* put *pp[j] where it belongs */ 1N/A i =
pp[j] - q;
/* the index in q of the element 1N/A pp[j] = q + j;
/* this is ok now */ 1N/A }
while ((j = i) != n);
1N/A /* There are only finitely many (nmemb) addresses 1N/A * So we must eventually revisit an index we saw before. 1N/A * Suppose the first revisited index is k != n. 1N/A * An index is visited because something else belongs there. 1N/A * If we visit k twice, then two different elements must 1N/A * belong in the same place, which cannot be. 1N/A * So j must get back to n, the loop terminates, 1N/A * and we put the saved element where it belongs. 1N/A q[n] =
tmp;
/* put what belongs into 1N/A * the n-th element */ 1N/A /* free iff allocated */ 1N/A /* restore prevailing comparison routine */ 1N/A=head1 Array Manipulation Functions 1N/ASort an array. Here is an example: 1N/A sortsv(AvARRAY(av), av_len(av)+1, Perl_sv_cmp_locale); 1N/ASee lib/sort.pm for details about controlling the sorting algorithm. 1N/A /* Sun's Compiler (cc: WorkShop Compilers 4.2 30 Oct 1996 C 4.2) used 1N/A to miscompile this function under optimization -O. If you get test 1N/A errors related to picking the correct sort() function, try recompiling 1N/A this file without optimiziation. -- A.D. 4/2002. 1N/A /* The default as of 5.8.0 is mergesort */ 1N/A /* optimiser converts "@a = sort @a" to "sort \@a"; 1N/A * in case of tied @a, pessimise: push (@a) onto stack, then assign 1N/A * result back to @a at the end of this function */ 1N/A (
void)
POPMARK;
/* remove mark associated with ex-OP_AASSIGN */ 1N/A /* shuffle stack down, removing optional initial cv (p1!=p2), plus any 1N/A * nulls; also stringify any args */ 1N/A if ((*
p1 = *
p2++)) {
/* Weed out nulls. */ 1N/A /* This is mostly copied from pp_entersub */ 1N/A#
endif /* USE_5005THREADS */ 1N/A MEXTEND(
SP,
20);
/* Can't afford stack realloc on signal. */ 1N/A /* simulate pp_aassign of tied AV */