Re: Is Sort stable?

*To*: mathgroup at smc.vnet.net*Subject*: [mg39773] Re: Is Sort stable?*From*: Paul Abbott <paul at physics.uwa.edu.au>*Date*: Fri, 7 Mar 2003 03:30:17 -0500 (EST)*Organization*: The University of Western Australia*References*: <b41bv1$pea$1@smc.vnet.net> <b440eu$165$1@smc.vnet.net> <b46u2m$924$1@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

In article <b46u2m$924$1 at smc.vnet.net>, "Roland Nilsson" <rolle at ifm.liu.se> wrote: > I think there was some terminology confusion here. Sorting algorithms are > referred to as "stable" (in my world at least) when elements that are *not* > different with respect to the order are guaranteed *not to be rearranged*. > I.e., sorting the list > > (1, 2) > (2, 3) > (1, 4) > (3 ,4) > > w.r.t. the first column only will always yield > > (1, 2) > (1, 4) > (2, 3) > (3 ,4) > > with a *stable* sort algorithm. Unstable sorting rearrange (1,2) and > (1,4) at will. It seems to me from the discussion in this thread that Mathematica's Sort > does reverse such elements. It is interesting to use Trace to try to see what is happening here: data = {{1, 4}, {1, 2}, {3, 4}, {2, 3}}; Trace[Sort[data, #1[[1]] < #2[[1]] & ]] // TableForm Trace[Sort[data, #1[[1]] <= #2[[1]] & ]] // TableForm Cheers, Paul -- Paul Abbott Phone: +61 8 9380 2734 School of Physics, M013 Fax: +61 8 9380 1014 The University of Western Australia (CRICOS Provider No 00126G) 35 Stirling Highway Crawley WA 6009 mailto:paul at physics.uwa.edu.au AUSTRALIA http://physics.uwa.edu.au/~paul