Require sort to be stable for fill elements of elements

2 files changed, 2 insertions, 2 deletions

diff --git a/docs/spec/primitive.html b/docs/spec/primitive.html
index e59188d1..8a7a9a70 100644
--- a/docs/spec/primitive.html
+++ b/docs/spec/primitive.html
@@ -145,7 +145,7 @@
 <p><strong>Find</strong> (<code><span class='Function'>⍷</span></code>) indicates positions where <code><span class='Value'>𝕨</span></code> appears as a contiguous subarray of a <code><span class='Function'>=</span><span class='Value'>𝕨</span></code>-cell of <code><span class='Value'>𝕩</span></code>. It has one result element for each such subarray of <code><span class='Value'>𝕩</span></code>, whose value is 1 if that subarray matches <code><span class='Value'>𝕩</span></code> and 0 otherwise.</p>
 <h3 id="sorting">Sorting</h3>
 <p>Sorting functions are those that depend on BQN's array ordering. There are three kinds of sorting function, with two functions of each kind: one with an upward-pointing glyph that uses an ascending ordering (these function names are suffixed with &quot;Up&quot;), and one with a downward-pointing glyph and the reverse, descending, ordering (&quot;Down&quot;). Below, these three kinds of function are described, then the ordering rules. Except for the right argument of Bins, all arguments must have rank at least 1.</p>
-<p><strong>Sort</strong> (<code><span class='Function'>∧∨</span></code>) reorders the major cells of its argument so that a major cell with a lower index comes earlier in the ordering than a major cell with a higher index, or matches it.</p>
+<p><strong>Sort</strong> (<code><span class='Function'>∧∨</span></code>) reorders the major cells of its argument so that a major cell with a lower index comes earlier in the ordering than a major cell with a higher index, or matches it. If it's possible for matching arrays to differ in behavior because of different (including undefined versus defined) fill elements, then these arrays must maintain their ordering (a stable sort is required).</p>
 <p><strong>Grade</strong> (<code><span class='Function'>⍋⍒</span></code>) returns a permutation describing the way the argument array would be sorted. For this reason the reference implementations simply define Sort to be selection by the grade. One way to define Grade is as a sorted version of the index list <code><span class='Function'>↕≠</span><span class='Value'>𝕩</span></code>. An index <code><span class='Value'>i</span></code> is ordered according to the corresponding major cell <code><span class='Value'>i</span><span class='Function'>⊏</span><span class='Value'>𝕩</span></code>. However, ties in the ordering are broken by ordering the index values themselves, so that no two indices are ever considered equal, and the result of sorting is well-defined (for Sort this is not an issue—matching cells are truly interchangeable). This property means that a stable sorting algorithm must be used to implement Grade functions. While cells might be ordered ascending or descending, indices are always ordered ascending, so that for example index <code><span class='Value'>i</span></code> is placed before index <code><span class='Value'>j</span></code> if either <code><span class='Value'>i</span><span class='Function'>⊏</span><span class='Value'>𝕩</span></code> comes earlier in the ordering than <code><span class='Value'>j</span><span class='Function'>⊏</span><span class='Value'>𝕩</span></code>, or if they match and <code><span class='Value'>i</span><span class='Function'>&lt;</span><span class='Value'>j</span></code>.</p>
 <p><strong>Bins</strong> (<code><span class='Function'>⍋⍒</span></code>) requires the <code><span class='Value'>𝕨</span></code> to be ordered in the sense of Sort (with the same direction). Like a dyadic search function, it then works on cells of <code><span class='Value'>𝕩</span></code> with the same rank as major cells of <code><span class='Value'>𝕨</span></code>: the rank of <code><span class='Value'>𝕩</span></code> cannot be less than <code><span class='Paren'>(</span><span class='Function'>=</span><span class='Value'>𝕨</span><span class='Paren'>)</span><span class='Function'>-</span><span class='Number'>1</span></code>. For each of these, it identifies where in the ordering given by <code><span class='Value'>𝕨</span></code> the cell belongs, that is, the index of the first cell in <code><span class='Value'>𝕨</span></code> that is ordered later than it, or <code><span class='Function'>≠</span><span class='Value'>𝕨</span></code> if no such cell exists. An equivalent formulation is that the result value for a cell of <code><span class='Value'>𝕩</span></code> is the number of major cells in <code><span class='Value'>𝕨</span></code> that match or precede it.</p>
 <p>BQN's <em>array ordering</em> is an extension of the number and character ordering given by <code><span class='Function'>≤</span></code> to arrays. In this system, any two arrays consisting of only numbers and characters for atoms can be compared with each other. Furthermore, some arrays that contain incomparable atoms (operations) might be comparable, if the result of the comparison can be decided before reaching these atoms. Array ordering does not depend on the fill elements for the two arguments.</p>
diff --git a/spec/primitive.md b/spec/primitive.md
index 829729f8..24f98e6d 100644
--- a/spec/primitive.md
+++ b/spec/primitive.md
@@ -183,7 +183,7 @@ Dyadic search functions check whether major cells of the *principal argument* (w
 
 Sorting functions are those that depend on BQN's array ordering. There are three kinds of sorting function, with two functions of each kind: one with an upward-pointing glyph that uses an ascending ordering (these function names are suffixed with "Up"), and one with a downward-pointing glyph and the reverse, descending, ordering ("Down"). Below, these three kinds of function are described, then the ordering rules. Except for the right argument of Bins, all arguments must have rank at least 1.
 
-**Sort** (`∧∨`) reorders the major cells of its argument so that a major cell with a lower index comes earlier in the ordering than a major cell with a higher index, or matches it.
+**Sort** (`∧∨`) reorders the major cells of its argument so that a major cell with a lower index comes earlier in the ordering than a major cell with a higher index, or matches it. If it's possible for matching arrays to differ in behavior because of different (including undefined versus defined) fill elements, then these arrays must maintain their ordering (a stable sort is required).
 
 **Grade** (`⍋⍒`) returns a permutation describing the way the argument array would be sorted. For this reason the reference implementations simply define Sort to be selection by the grade. One way to define Grade is as a sorted version of the index list `↕≠𝕩`. An index `i` is ordered according to the corresponding major cell `i⊏𝕩`. However, ties in the ordering are broken by ordering the index values themselves, so that no two indices are ever considered equal, and the result of sorting is well-defined (for Sort this is not an issue—matching cells are truly interchangeable). This property means that a stable sorting algorithm must be used to implement Grade functions. While cells might be ordered ascending or descending, indices are always ordered ascending, so that for example index `i` is placed before index `j` if either `i⊏𝕩` comes earlier in the ordering than `j⊏𝕩`, or if they match and `i<j`.