Mercurial > hg > xemacs-beta

comparison lib-src/qsort.c @ 444:576fb035e263 r21-2-37

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Import from CVS: tag r21-2-37
author cvs
date Mon, 13 Aug 2007 11:36:19 +0200
parents 376386a54a3c
children 061f4f90f874
comparison
equal deleted inserted replaced
443:a8296e22da4e 444:576fb035e263
62 next array partition to sort. To save time, this maximum amount 62 next array partition to sort. To save time, this maximum amount
63 of space required to store an array of MAX_INT is allocated on the 63 of space required to store an array of MAX_INT is allocated on the
64 stack. Assuming a 32-bit integer, this needs only 32 * 64 stack. Assuming a 32-bit integer, this needs only 32 *
65 sizeof (stack_node) == 136 bits. Pretty cheap, actually. 65 sizeof (stack_node) == 136 bits. Pretty cheap, actually.
66 66
67 2. Chose the pivot element using a median-of-three decision tree. 67 2. Choose the pivot element using a median-of-three decision tree.
68 This reduces the probability of selecting a bad pivot value and 68 This reduces the probability of selecting a bad pivot value and
69 eliminates certain extraneous comparisons. 69 eliminates certain extraneous comparisons.
70 70
71 3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving 71 3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving
72 insertion sort to order the MAX_THRESH items within each partition. 72 insertion sort to order the MAX_THRESH items within each partition.