diff options
author | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2021-01-14 13:26:55 -0300 |
---|---|---|
committer | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2021-01-14 13:26:55 -0300 |
commit | 825ac8eca8e384d6ad2538b5670088c31e08a9d7 (patch) | |
tree | 14a92070cf251a1fc93246e92562ac2855dc676d | |
parent | b07fc10e91a5954254b47280aba287220c734a4b (diff) | |
download | lua-github-825ac8eca8e384d6ad2538b5670088c31e08a9d7.tar.gz |
Corrected documentation for 'table.sort'
The sort function must define a (strict) weak order for a correct
sorting. A partial order is not enough.
-rw-r--r-- | manual/manual.of | 16 |
1 files changed, 8 insertions, 8 deletions
diff --git a/manual/manual.of b/manual/manual.of index 09297a63..2fe332a4 100644 --- a/manual/manual.of +++ b/manual/manual.of @@ -7821,19 +7821,19 @@ from @T{list[1]} to @T{list[#list]}. If @id{comp} is given, then it must be a function that receives two list elements and returns true when the first element must come -before the second in the final order -(so that, after the sort, -@T{i < j} implies @T{not comp(list[j],list[i])}). +before the second in the final order, +so that, after the sort, +@T{i <= j} implies @T{not comp(list[j],list[i])}. If @id{comp} is not given, then the standard Lua operator @T{<} is used instead. -Note that the @id{comp} function must define -a strict partial order over the elements in the list; -that is, it must be asymmetric and transitive. -Otherwise, no valid sort may be possible. +The @id{comp} function must define a consistent order; +more formally, the function must define a strict weak order. +(A weak order is similar to a total order, +but it can equate different elements for comparison purposes.) The sort algorithm is not stable: -elements considered equal by the given order +Different elements considered equal by the given order may have their relative positions changed by the sort. } |