# Understanding issorted's lt keyword

**URL:** <https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918>\
**Category:** New to Julia\
**Created:** [May 10, 2021, 9:34pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918 "2021-05-10T21:34:36Z")\
**Posts on this page:** 20\
**Page:** 3

<div class="post-metadata">

**Author:** ![sostock](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sostock/32/5546_2.png) [@sostock](https://discourse.julialang.org/u/sostock)\
**Post date:** [May 12, 2021, 11:29am UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/41 "2021-05-12T11:29:38Z")

</div>

> [@DNF](#):
>
> Where is this made explicit? The closest I could find was
> 
> > the `lt` keyword allows providing a custom “less than” function
> 
> in the manual, and nothing in the docstring.

That part from the manual is what I meant, and I think it should definitely be added to the docstring.

> [@DNF](#):
>
> But it does actually accept “lesser than or equal”, since `issorted([1,2,2,3])` is `true` , and that is only sorted if equal is accepted as “less than”.

`issorted([1,2,2,3])` uses `isless`, which is a “lesser than” function, not a “lesser than or equal” function.

---

<div class="post-metadata">

**Author:** ![FPGro](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fpgro/32/20822_2.png) [@FPGro](https://discourse.julialang.org/u/FPGro)\
**Post date:** [May 12, 2021, 11:32am UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/42 "2021-05-12T11:32:50Z")

</div>

> [@sostock](#):
>
> `issorted([1,2,2,3])` uses `isless` , which is a “lesser than” function, not a “lesser than or equal” function.

Is that not exactly the source of this confusion? `issorted` achieves the `or equal` part because it does not actually assert that the input is sorted, it instead asserts that there are no consecutive elements that are sorted in reverse according to `lt`, which is also profoundly non-intuitive to me

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [May 12, 2021, 11:33am UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/43 "2021-05-12T11:33:09Z")

</div>

> [@sostock](#):
>
> That part from the manual is what I meant

I see nothing about ‘strict total order’ there, only a loose “less than”, which I take to have a conversational, non-formal meaning. “strict total order” is an obscure concept, even for people with maths degrees, I wouldn’t expect most users to have heard of it.

> [@sostock](#):
>
> `issorted([1,2,2,3])` uses `isless` , which is a “lesser than” function, not a “lesser than or equal” function.

I know it does, but the _behaviour_ is that every element is “less than or equal” to the next.

Is every element in `[1,2,2,3]` strictly less than the next element? If not, how can one say it is sorted according to a strict total ordering?

---

<div class="post-metadata">

**Author:** ![sostock](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sostock/32/5546_2.png) [@sostock](https://discourse.julialang.org/u/sostock)\
**Post date:** [May 12, 2021, 12:15pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/44 "2021-05-12T12:15:57Z")

</div>

Let’s stop talking about the Julia implementation for a second: Every _total order relation_ \leq has an associated _strict total order relation_ \< and vice versa. both relations (\leq and \<) can be used to describe the same ordering.

> [@DNF](#):
>
> Is every element in `[1,2,2,3]` strictly less than the next element? If not, how can one say it is sorted according to a strict total ordering?

The way I see it, it is sorted according to a specified order, which in Julia is supplied via a \< relation. In theory, when describing an order, it does not matter whether one uses the non-reflexive (\<) relation or the reflexive (\leq) relation to describe that order. But an actual implementation of a sorting algorithm needs to know whether it is working with a \< or a \leq relation, otherwise it might produce garbage.

It was decided that the Julia sorting machinery uses the \< relation for describing an order, not the \leq relation. I don’t know why this was chosen. Maybe it was easier to implement the sorting algorithms that way, maybe it’s just because there is an `isless` function but no `islessorequal` function.

I can see that this decision to use \< instead of \leq to describe orders seems wrong if you assume that

> [@DNF](#):
>
> ```julia
> issorted([a, b]; lt=foo) <==> foo(a, b)
> 
> ```

should hold.

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [May 12, 2021, 12:25pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/45 "2021-05-12T12:25:12Z")

</div>

So the thing is that this is an extremely subtle point, unless you have a degree in this specific area. For a very ‘ordinary’, common, functionality that probably most users _think_ they grasp intuitively, the documentation would need a very dramatic beefing up.

I mean, is it reasonable to expect that people should be well-versed in set theory to be able to use a normal sort function?

---

<div class="post-metadata">

**Author:** ![Sukera](https://avatars.discourse-cdn.com/v4/letter/s/ce7236/32.png) [@Sukera](https://discourse.julialang.org/u/Sukera)\
**Post date:** [May 12, 2021, 12:27pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/46 "2021-05-12T12:27:39Z")

</div>

Some sorting algorithms are sensitive to whether \le or \lt is used, because they may depend on the initial order the to-be-sorted elements (that are =) appear in. Sorting algorithms that preserve that order between equal elements are called [stable](https://en.wikipedia.org/wiki/Sorting_algorithm#Stability) (there may be some other distinguishing feature the sorting implementation in question isn’t aware of). It may be that if \le were the default, we’d have a harder time implementing these (or they wouldn’t be as efficient as possible?).

Sorting and knowing what order to sort by is not necessarily a trivial task.

---

<div class="post-metadata">

**Author:** ![Jean\_Michel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jean_michel/32/8282_2.png) [@Jean\_Michel](https://discourse.julialang.org/u/Jean_Michel)\
**Post date:** [May 12, 2021, 4:32pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/47 "2021-05-12T16:32:58Z")

</div>

Excuse me, I am jumping in the conversation after 46 posts, but I see immediately what is wrong.  
The Julia manual just uses the mathematical definition for what is a total order. A total order is given  
by a function \< such that

- for any a,b we have either a\<b or b\<a or a==b (but only one of them)
- if a\<b and b\<c then a\<c

In other words, a total order is what in this conversation you call “strict total order”.  
The operator \<= does not satisfy the axioms of a total order so should not be used with `sort` or `issorted`.

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [May 12, 2021, 5:15pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/48 "2021-05-12T17:15:15Z")

</div>

> [@Jean\_Michel](#):
>
> The operator \<= does not satisfy the axioms of a total order so should not be used with `sort` or `issorted` .

But then it becomes impossible to sort non-unique vectors, since they cannot obey a total ordering, so it doesn’t seem very useful.

Also, the docs don’t say you cannot use certain orderings, and the sort function does not reject `<=`.

I still don’t get what’s the big deal about ‘strict total order’. Why can’t you sort data in a loose, partial, laissez-faire, off-the-cuff order?

---

<div class="post-metadata">

**Author:** ![Jean\_Michel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jean_michel/32/8282_2.png) [@Jean\_Michel](https://discourse.julialang.org/u/Jean_Michel)\
**Post date:** [May 12, 2021, 5:21pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/49 "2021-05-12T17:21:08Z")

</div>

> [@DNF](#):
>
> But then it becomes impossible to sort non-unique vectors, since they cannot obey a total ordering, so it doesn’t seem very useful.

Not at all. When sorting a non-unique vector the equal elements will become consecutive. The algorithm in Julia for sort uses the definition I gave for sort and sorts perfectly well non-unique vectors  
and the result is `issorted`. The Julia devs used the mathematical definition for a total order to be able  
to follow books on sorting which use the same definition (read for example Knuth).

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [May 12, 2021, 5:23pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/50 "2021-05-12T17:23:40Z")

</div>

But how can it be sorted if each element isn’t `<` than the next? Each element is, however, `<=` than the next, so `<=` is the correct ordering.

What am I missing? This is really frustrating.

---

<div class="post-metadata">

**Author:** ![Jean\_Michel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jean_michel/32/8282_2.png) [@Jean\_Michel](https://discourse.julialang.org/u/Jean_Michel)\
**Post date:** [May 12, 2021, 5:29pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/51 "2021-05-12T17:29:41Z")

</div>

Given a total order \<, you can define a “less than or equal” relation \<= which is:

- a\<=b if a\<b or a=b

But this relation is _not_ a total order. A sequence a\_1,…,a\_n is sorted if a\_i\<a\_{i+1} or a\_i=a\_{i+1}, or  
in other terms a\_i\<=a\_{i+1}. The function you give to `sort` must be a total order, otherwise it will give  
unpredictable results, so even though a function \< can be used to define a function \<=, you should not give \<= as argument to sort (or `issorted`) otherwise it will misbehave.

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [May 12, 2021, 5:32pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/52 "2021-05-12T17:32:31Z")

</div>

I still don’t understand. I’ll quote my recent question:

> [@DNF](#):
>
> **But how can it be sorted if each element isn’t `<` than the next?** Each element is, however, `<=` than the next, so `<=` is the correct ordering.

---

<div class="post-metadata">

**Author:** ![gustaphe](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gustaphe/32/18174_2.png) [@gustaphe](https://discourse.julialang.org/u/gustaphe)\
**Post date:** [May 12, 2021, 5:40pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/53 "2021-05-12T17:40:41Z")

</div>

The way I see it, _should_-wise: `issorted` should simply check whether `lt` holds for each consecutive pair. `sort` should have an output for which `issorted` is true, if possible. The default `lt` should be `<=`. `sort([1, 1, 2]; lt=isless)` should error out, because it can’t be done, just like `sort([1, im]; lt=isless)` can’t be done.

Implementation wise, the possibility of using arbitrary comparisons means it can’t be entirely specialized on type (like above), and it’s not even guaranteed there is an algorithm, consider `lt=(x, y)->false`. But the domain of `lt` for `sort` is a strict subset of that for `issorted`.

---

<div class="post-metadata">

**Author:** ![Jeff\_Emanuel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jeff_emanuel/32/15440_2.png) [@Jeff\_Emanuel](https://discourse.julialang.org/u/Jeff_Emanuel)\
**Post date:** [May 12, 2021, 6:05pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/54 "2021-05-12T18:05:14Z")

</div>

The point of issorted is to check whether calling sort is useful or necessary. Think of it as asking “If I call sort with this value for its lt parameter, will it return the array unchanged?” You shouldn’t expect any more or less of it.

---

<div class="post-metadata">

**Author:** ![goretkin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goretkin/32/167_2.png) [@goretkin](https://discourse.julialang.org/u/goretkin)\
**Post date:** [May 12, 2021, 6:05pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/55 "2021-05-12T18:05:37Z")

</div>

> [@gustaphe](#):
>
> The way I see it, _should_ -wise: `issorted` should simply check whether `lt` holds for each consecutive pair.

That means that the default `lt = isless` would be wrong, since it would give `issorted([1, 1]) == false`.

You could then suggest the default be `lt = <=`, but note that the fallback for `<=` is defined in terms of `<`:

> <https://github.com/JuliaLang/julia/blob/d6c092d6d73be9b41b5b8fef30d882fdb63a8d20/base/operators.jl#L401>

And `<` is defined in terms of `isless`:

> <https://github.com/JuliaLang/julia/blob/d6c092d6d73be9b41b5b8fef30d882fdb63a8d20/base/operators.jl#L352>

If you simply define `isless` and `==` (EDIT: not `isequal`), you get the desired (probably) definitions of the other operators. I’d say that this is nothing more than a design choice, but it’s one that works pretty well in my opinion. And indeed you can write `issorted` in terms of `isless`: instead of checking that every consecutive element satisfies a property, you instead check that no consecutive element violates a property.

I understand that this extra negation and swapping of the arguments is not the first definition of `issorted` that some people are thinking of. But the definition that _is_ in `Base` is self-consistent. That’s not to say that this can’t be better documented.

I’ll add that there might be cases where it’s better to define `isless` on your type (possible a wrapper type) than it is to pass in a function for `lt`. I asked about these two choices once upon a time: [Designing APIs. defining new methods versus passing in functions](https://discourse.julialang.org/t/designing-apis-defining-new-methods-versus-passing-in-functions/18699)

> [@Designing APIs. defining new methods versus passing in functions](https://discourse.julialang.org/t/designing-apis-defining-new-methods-versus-passing-in-functions/18699/3):
>
> Once you define `isless` on your type (your thing), then you can use `min` , `minimum` , `sort` , you can use the lexicographic ordering induced by `isless` on `NTuple{Thing}` , and so forth. (So, here’s a benefit of the second API)

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [May 12, 2021, 6:13pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/56 "2021-05-12T18:13:16Z")

</div>

> [@goretkin](#):
>
> instead of checking that every consecutive element satisfies a property, you instead check that no consecutive element violates a property.

Actually, it seems that the current implementation checks whether the reverse order does _not_ satisfy the property, and those are not equivalent, thus causing all this confusion.

> [@Jeff\_Emanuel](#):
>
> The point of issorted is to check whether calling sort is useful or necessary.

That seems backwards to me. The fundamental concept is being sorted, while sorting is just any algorithm that causes a sequence to be sorted. This definition is at least much easier to explain. I get a bit of a headache trying to grasp the ‘inverse’ definition of the concepts, that you are advocating.

---

<div class="post-metadata">

**Author:** ![goretkin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goretkin/32/167_2.png) [@goretkin](https://discourse.julialang.org/u/goretkin)\
**Post date:** [May 12, 2021, 6:17pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/57 "2021-05-12T18:17:04Z")

</div>

> [@DNF](#):
>
> Actually, it seems that the current implementation checks whether the reverse order does _not_ satisfy the property, and those are not equivalent, thus causing all this confusion.

I might have been unclear. To emphasize, I said “a property”, and you’re talking about “the property”. Once someone understand that the property is not `lt(this_element, next_element)`, but instead `!lt(next_element, this_element)`, I don’t see what confusion remains.

And I’ll argue that you don’t need to look at the implementation to know that that’s what’s happening, if you understand that the default value of `lt` is `isless`, and that `issorted` accepts any function for `lt`.

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [May 12, 2021, 6:21pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/58 "2021-05-12T18:21:46Z")

</div>

And I _do_ understand that this is the case. It just seems completely bizarre.

Why is it done like this? Why not then supply a “greater than” comparison?

I realize this won’t change, and is probably ‘correct’. It’s just so mind-bendingly, brain-explodingly counterintuitive. I wish I could ‘get it’.

---

<div class="post-metadata">

**Author:** ![goretkin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goretkin/32/167_2.png) [@goretkin](https://discourse.julialang.org/u/goretkin)\
**Post date:** [May 12, 2021, 6:23pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/59 "2021-05-12T18:23:57Z")

</div>

> [@DNF](#):
>
> I get a bit of a headache trying to grasp the ‘inverse’ definition of the concepts, that you are advocating.

Note that I am justifying the definition of `issorted` by discussing the function `isless`. Julia (`Base` and software ecosystem) is unlike any other in my experience in how well it does _generic programming_. By design, `isless` and `isequal` is more “fundamental” than the `<=` that you are advocating for.

We are lucky when outcomes of careful design for generic programming aligns with the expectations of every user, and we appear not to be lucky this time. It is obvious to me that the solution is better documentation, instead of re-working how comparisons are done in Julia.

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [May 12, 2021, 6:28pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/60 "2021-05-12T18:28:19Z")

</div>

> [@goretkin](#):
>
> By design, `isless` and `isequal` is more “fundamental” than the `<=` that you are advocating for.

But what’s the relevance of that? The question I’m struggling with is “what does it mean for a sequence to be sorted according to some comparison operator?”

This switching of order and negation causes weird results, and the motivation is opaque to me.

[Previous page](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918.md?page=2)

[Next page](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918.md?page=4)