What Nick said is interesting, and a little puzzling at
first thought. The problem that different results are
returned for the same input is indeed possible, if any
randomized algorithm, for example, randomized quicksort, is
used during -sort-. (I do not know which sort algorithm(s)
Stata uses.)
One version of randomizations is, as Nick described, to
permute the original input before any sorting is done. As I
understand, the main purpose of this extra step is to make
sure the performance of quicksorting is independent of the
original input. That is, after randomization, sorting will
achieve expected efficiency most of the time, even when the
original input is badly ordered. In the jargons of computer
scientist, for any input, most randomizations will cause
quicksort to perform nearly as well as the average case of O
(nlgn).
Jingsong Cui
Department of Economics
Temple University
Nick said:
---- Original message ----
>Date: Tue, 10 Jun 2003 22:54:10 +0100
>From: "Nick Cox" <[email protected]>
>Subject: st: RE: is ordering with -bysort- unique?
>To: <[email protected]>
>Will the answer be the same? In general, I doubt it.
>At least some of the time Stata appears to randomize
>the order a little before -sort-ing, although I can't
>remember why I think I know that; anyway, I doubt that the
answer
>is reproducible. I wouldn't depend on it.
>
>Nick
>[email protected]
>
*
* For searches and help try:
* http://www.stata.com/support/faqs/res/findit.html
* http://www.stata.com/support/statalist/faq
* http://www.ats.ucla.edu/stat/stata/
