MathGroup Archive 1999

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Sorting problem

  • To: mathgroup at
  • Subject: [mg20112] Re: [mg20071] Sorting problem
  • From: "Andrzej Kozlowski" <andrzej at>
  • Date: Thu, 30 Sep 1999 02:43:18 -0400
  • Sender: owner-wri-mathgroup at

I don't want to sound rude but I do not think this problem is really so 
interesting or very relevant to this group. Or rather, more precisely, this
kind of questions surface here from time to time but usually lead to
anything fruitful. The reasons are as follows.

There is nothing at all mysterious about the theoretical question itself. It
is very well known and discussed in detail in Section 5.3.3 of Volume 3 of
Knuth's "The Art of Computer Programming" (1973 edition). The method is
described in Section 5.2.3 and called "tree selection". (the algorithm
itself is on page 142). This can be easily implemented in Mathematica but it
seems to me that is not much point doing so. The reason is that the actual
function you will get will almost certainly perform worse in real life than
something constructed using built in functions, even if it's theoretical
running time of the algorithm is worse. For example, here is one obvious

secondlargest[l_] := Max[DeleteCases[l, Max[l]]]

It seems to me that this should have the worst case running time of 3n-3,
but most likely will beat a user defined implementation of the best
algorithm. And if not than probably something similar will. It may be mildly
interesting to check this hypothesis but I have seen already enough evidence
that this sort of thing is true in general. Of course there is another
possible question here: would it be useful to have a built in implementation
of a (generalized) algorithm of this type? I guess it probably just wouldn't
be useful enough.

In my opinion Mathematica has to be treated as a separate computing paradigm
and efficiency comparisons only make sense between different Mathematica
functions based on actual performance (which in any case may be platform

Andrzej Kozlowski
Toyama International University

>From: Cheng Tsz Hei <s986001 at>
To: mathgroup at
>To: mathgroup at
>Subject: [mg20112] [mg20071] Sorting problem
>Date: Wed, Sep 29, 1999, 16:33

> Dear everybody,
>      Here I have some interesting problem want to share with everyone.
> The problem is :
>        there are n elements in the arrays and we would like to find the
> second smallest
> one in at most n + lgn - 2 comparsion in the worest case.
>       anyone know the answer?
> Maths

  • Prev by Date: Re: checking for overlap
  • Next by Date: Re: Q: NSolve with conditions
  • Previous by thread: Sorting problem
  • Next by thread: iMath integrates with MathScript