Re: Sorting and "ordering functions"
- To: mathgroup at yoda.physics.unc.edu
- Subject: Re: Sorting and "ordering functions"
- From: keiper
- Date: Tue, 8 Dec 92 10:03:22 CST
JWENDEL at isdmnl.wr.usgs.gov writes:
> The main question suggested is: what is an ordering function
> p as cited on pg 870 of the Mma book; can it be any function of
> two variables, or must it have properties such as transitivity
> (x<y and x<z -> x<z) and non-reflexivity (x<x is False)?
Non-reflexivity is not an issue, but unless transitivity is assumed, any
sorting algorithm will be O(n^2): you simply have to compare all pairs.
This is simply unacceptable when any respectable sorting algorithm is
O(n log(n)). Because transitivity is assumed (verifying that it is would
be silly) you will get unpredictable results if it is in fact not transitive.
Just for the record, the sort used is a merge sort. The reason is that
even in the worst case few comparisons are needed.
Jerry B. Keiper
keiper at wri.com