MathGroup Archive 2003

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

Search the Archive

Re: Is Sort stable?


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?