sort inefficiency

Dylan Thurston dpt@math.harvard.edu
Wed, 3 Apr 2002 01:47:37 -0500


--oC1+HKm2/end4ao3
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

On Wed, Apr 03, 2002 at 09:35:51AM +0400, Serge D. Mechveliani wrote:
> The Standard library specifies only the  map  related to the name=20
> `sort'. This map can be described, for example, via sort-by-insertion
> program.
> And the algorithm choice is a matter of each particular
> implementation. Implementation has right to change the algorithm.

Reading this, it occurred to me that if you're very picky the
implementation probably isn't allowed to pick the algorithm: you need to
assume that '<' is actually a total order to have much leeway at all.
(Suppose, e.g., that comparing two particular elements yields an
exception.)

It seems to me this is a problem with providing code as specification:
you probably fix the details more than you want.

Best,
	Dylan Thurston

--oC1+HKm2/end4ao3
Content-Type: application/pgp-signature
Content-Disposition: inline

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iD8DBQE8qqWJVeybfhaa3tcRAr25AJsECoaOzp8lcs1Gni0R0x7tAbNsqQCZAdU2
lYTw9jtZeYwOqvk2BQARyLg=
=j2GJ
-----END PGP SIGNATURE-----

--oC1+HKm2/end4ao3--