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

```

• Prev by Date: Re: Is Sort stable?
• Next by Date: Re: Solving a system of Inequalities
• Previous by thread: Re: Is Sort stable?
• Next by thread: Re: Re: Is Sort stable?