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.