[Date Prev][Date Next][Thread Prev][Thread Next][Date index][Thread index]
Re: st: RE: is ordering with -bysort- unique?
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)
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
Department of Economics
---- Original message ----
>Date: Tue, 10 Jun 2003 22:54:10 +0100
>From: "Nick Cox" <email@example.com>
>Subject: st: RE: is ordering with -bysort- unique?
>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
>is reproducible. I wouldn't depend on it.
* For searches and help try: