tree 938b4c7405fb38d37cffc55c12d1aa8b5a9375f7
parent a1c85ed83ef0c9e11374caf14ec7aff6b716329d
author Russ Cox <rsc@golang.org> 1226951494 -0800
committer Russ Cox <rsc@golang.org> 1226951494 -0800
golang-hg 6077f747facc89bfd44fa949855c2bb064589e00

adopt suggestions from Bentley and McIlroy (SP&E Nov 1993)
to make qsort more robust:

	* use "ninther" to choose pivot.
	* use three-way partition to avoid quadratic
 	  behavior on all-one-value arrays.

also add tests suggested in that paper.

the immediate cause of the slowness we observed was
in fact none of these: the recursive call was sorting
data[0:m] instead of data[a:m].

also rename package to "sort" to match convention.

R=r,gri
DELTA=358  (255 added, 21 deleted, 82 changed)
OCL=19341
CL=19373