What "Sort" option of ...Values does?

Question

All the ..Values functions have undocumented option Sort:

In[1]:= Options /@ {OwnValues, DownValues, UpValues, SubValues, 
  DefaultValues, FormatValues, NValues}

Out[1]= {{Sort -> True}, {Sort -> True}, {Sort -> True}, {Sort -> 
   True}, {Sort -> True}, {Sort -> True}, {Sort -> True}}

What this option does and for which purposes it may be useful?

Answer 1

When you enter your definitions for a function, you enter them in a particular order. In case when your definitions do not contain patterns, they are stored internally in a hash table. When you request them, they will be sorted by default:

In[11]:= 
Clear[g];
g[5]=1;
g[4]=2;
g[3]=3;

In[15]:= DownValues[g]
Out[15]= {HoldPattern[g[3]]:>3,HoldPattern[g[4]]:>2,HoldPattern[g[5]]:>1}

However, often you may want to see the original order in which the values were assigned. Here is how:

In[16]:= DownValues[g,Sort->False]
Out[16]= {HoldPattern[g[5]]:>1,HoldPattern[g[4]]:>2,HoldPattern[g[3]]:>3}

An example of one instance where you may want to use it, is when you need to implement a cache (my attempt to do that based on this option can be found here). For a large number of definitions, however, it is probably not guaranteed that the definitions will follow in the original order, since the internal hash-tables will probably be expanded and rehashed several times. Generically, a hash table implementation does not guarantee the order in which the key-value pairs are stored. So, what you achieve by setting Sort->False is that the ...Values are not sorted by Mathematica before they are returned to you, so you get them pretty much in the order Mathematica currently stores them.

Another case when you may want this is when you want to build a dictionary-like structure using DownValues - in this case, key extraction will be much faster with Sort->False, since no sorting on the key set has to be performed (matters for large key sets):

In[31]:= 
 Clear[gg];
(gg[#]:=200000-#)&/@Range[200000];

In[33]:= DownValues[gg][[All,1,1,1]]//Short//Timing
Out[33]= {4.867,{1,2,3,<<199994>>,199998,199999,200000}}

In[34]:= DownValues[gg,Sort->False][[All,1,1,1]]//Short//Timing
Out[34]= {2.103,{95090,102286,<<199996>>,38082,26686}}

You can find an example of such use e.g. here.

As far as I know, the Sort option only affects the non-pattern-based DownValues (and other ...Values), because for pattern-based DownValues Mathematica anyway attempts to reorder them in the order of their generality, as it understands that. OTOH, for pattern-based DownValues, you may do manual rule reordering and Mathematica will keep your changes, while for definitions without patterns, attempts to reorder the definitions manually after they were originally given seem to have no effect on them (perhaps, again because they are hashed internally, and hash-tables don't generally care about order).