• Russ Cox's avatar
    adopt suggestions from Bentley and McIlroy (SP&E Nov 1993) · 5aa7dc5d
    Russ Cox authored
    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
    5aa7dc5d
sorting.go 4.96 KB