MathGroup Archive 2011

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

Search the Archive

Re: reliably sort?

  • To: mathgroup at smc.vnet.net
  • Subject: [mg123755] Re: reliably sort?
  • From: Bill Rowe <readnews at sbcglobal.net>
  • Date: Sat, 17 Dec 2011 02:47:55 -0500 (EST)
  • Delivered-to: l-mathgroup@mail-archive0.wolfram.com

On 12/16/11 at 5:54 AM, ulrich.arndt at data2knowledge.de (Ulrich Arndt)
wrote:

>Union and Sort seems not naturally connected to me. Union is a set
>operation and according to the documentation it seems that the
>implementation is using some sorting...

As mathematical operations union and sort are not connected.
That is there is no mathematical reason to sort a group of items
to do the mathematical operation of union. But, you need to keep
in mind the practical implementation of these operations on a computer.

To perform an union (on an unordered set) you would need to
compare each element with every other element, i.e., n^2
compares. But if the set is sorted, you only need compare each
element to the next element for n compares. Since there are sort
algorithms that are more efficient than n^2, the most efficient
way to implement union is to first use an efficient sort
algorithm then do the union. Although I don't work for Wolfram
and do not have access to the source code for Mathematica, I am
certain Union does a Sort for the reason I've outlined.




  • Prev by Date: Re: Table constructed from two lists
  • Next by Date: Re: Table constructed from two lists
  • Previous by thread: Re: reliably sort?
  • Next by thread: Re: reliably sort?