# 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:** 1

<div class="post-metadata">

**Author:** ![mkitti](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mkitti/32/12459_2.png) [@mkitti](https://discourse.julialang.org/u/mkitti)\
**Post date:** [May 10, 2021, 9:34pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/1 "2021-05-10T21:34:36Z")

</div>

The `lt` keyword for `issorted` and `sort!` is defying my intuition. From reading the source code, I understand why I get the following results, but I am finding it counterintuitive.

From the documentation for `sort!`:

> the lt keyword allows providing a custom “less than” function

Let’s try it:

```julia
julia> issorted([1, 2, 3, 3])
true

julia> issorted([1, 2, 3, 3], lt = <)
true

julia> issorted([1, 2, 3, 3], lt = <=)
false

julia> issorted( sort([1, 2, 3, 4, 3], lt = <=), lt = <=)
false

```

I would think `confirm_sort(A, B) = issorted( sort( A, lt = B), lt = B)` would always evaluate to be `true`.

Can anyone explain how to think of the `lt` keyword intuitively?

---

<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 10, 2021, 9:59pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/2 "2021-05-10T21:59:04Z")

</div>

> [@mkitti](#):
>
> Can anyone explain how to think of the `lt` keyword intuitively?

```julia
help?> issorted
search: issorted InsertionSort

  issorted(v, lt=isless, by=identity, rev:Bool=false, order::Ordering=Forward)

  Test whether a vector is in sorted order. The lt, by and rev keywords modify what order is considered to be sorted just as they do for sort.

help?> sort
[...] 

  sort(v; alg::Algorithm=defalg(v), lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward)

```

The default `lt` function is `isless`.

```julia
help?> isless
[...]

  isless(x, y)

  Test whether x is less than y, according to a fixed total order. isless is not defined on all pairs of values (x, y). However, if it is defined, it is expected to satisfy the
  following:

    • If isless(x, y) is defined, then so is isless(y, x) and isequal(x, y), and exactly one of those three yields true.

```

Note that `lt = <=` does not satisfy that property, since for `x == y`, all three (`lt(x, y)`, `lt(y, x)`, `isequal(x, y)`) are `true`.

˜ ~~Perhaps more intuitively, ask yourself how you might implement `issorted`, and what you’d expect it to be able to do just given the `<=` function?~~~ [Edit: I’m not sure what I had meant by this]

---

<div class="post-metadata">

**Author:** ![jzr](https://avatars.discourse-cdn.com/v4/letter/j/eb9ed0/32.png) [@jzr](https://discourse.julialang.org/u/jzr)\
**Post date:** [May 10, 2021, 10:03pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/3 "2021-05-10T22:03:34Z")

</div>

I don’t see how that explains

```julia
julia> issorted([1,1], lt=<=)
false

```

---

<div class="post-metadata">

**Author:** ![mkitti](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mkitti/32/12459_2.png) [@mkitti](https://discourse.julialang.org/u/mkitti)\
**Post date:** [May 10, 2021, 10:05pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/4 "2021-05-10T22:05:41Z")

</div>

Part of the reason I am interested in `lt = <=` is that I actually want to verify that an iterable is both sorted and unique. I want the sequence to be strictly monotonically increasing, not just sorted.

My intuition would have been to indicate `lt = <` to accomplish that, but that is wrong.

---

<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 10, 2021, 10:13pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/5 "2021-05-10T22:13:35Z")

</div>

You are probably guessing at an implementation for `issorted` that is incorrect. It’s not that `lt(x, y)` must be satisfied for consecutive `x` and `y`. Otherwise `issorted([1, 1], lt=isless)` would be `false`.

---

<div class="post-metadata">

**Author:** ![jzr](https://avatars.discourse-cdn.com/v4/letter/j/eb9ed0/32.png) [@jzr](https://discourse.julialang.org/u/jzr)\
**Post date:** [May 10, 2021, 10:19pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/6 "2021-05-10T22:19:27Z")

</div>

> [@goretkin](#):
>
> It’s not that `lt(x, y)` must be satisfied for consecutive `x` and `y` .

What is it then?

---

<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 10, 2021, 10:22pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/7 "2021-05-10T22:22:08Z")

</div>

I think I see the pattern you are following, but ultimately `issorted` is likely to be the wrong concept, since you’re not asking if a list is sorted, but you’re asking if it’s strictly increasing. I think you should think of `issorted` as a verifier for `sort`. There’s nothing that `sort` can do to make some data strictly increasing and still look like a sort (it would have to e.g. discard some data).

Consider something instead like:

```julia
julia> using IterTools: partition

julia> all_consecutive_pairs(pred, itr) = all(Base.splat(pred), partition(itr, 2, 1))
all_consecutive_pairs (generic function with 1 method)

julia> all_consecutive_pairs(<, [1, 2, 3])
true

julia> all_consecutive_pairs(<, [1, 3, 3])
false

```

---

<div class="post-metadata">

**Author:** ![jzr](https://avatars.discourse-cdn.com/v4/letter/j/eb9ed0/32.png) [@jzr](https://discourse.julialang.org/u/jzr)\
**Post date:** [May 10, 2021, 10:33pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/8 "2021-05-10T22:33:45Z")

</div>

This still doesn’t make sense to me.

```julia
julia> issorted([1,1], lt=<=)
false

```

---

<div class="post-metadata">

**Author:** ![mkitti](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mkitti/32/12459_2.png) [@mkitti](https://discourse.julialang.org/u/mkitti)\
**Post date:** [May 10, 2021, 11:11pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/9 "2021-05-10T23:11:44Z")

</div>

Here is the source code for `issorted`:

[https://github.com/JuliaLang/julia/blob/bb5b98e72a151c41471d8cc14cacb495d647fb7f/base/sort.jl#L56-L68](https://github.com/JuliaLang/julia/blob/bb5b98e72a151c41471d8cc14cacb495d647fb7f/base/sort.jl#L56-L68)

[https://github.com/JuliaLang/julia/blob/bb5b98e72a151c41471d8cc14cacb495d647fb7f/base/sort.jl#L91-L93](https://github.com/JuliaLang/julia/blob/bb5b98e72a151c41471d8cc14cacb495d647fb7f/base/sort.jl#L91-L93)

Basically it goes over all the numbers. If the current number is “less than” the previous number, then it reports that the iterable is not sorted.

In the `issorted([1,1], lt=<=)` case, it instead asks if the current number is “less than or equal to” the previous number. If true, then it indicates the array is not sorted. The evaluation here boils down to

```julia
if 1 <= 1
    return false
end

```

---

<div class="post-metadata">

**Author:** ![jzr](https://avatars.discourse-cdn.com/v4/letter/j/eb9ed0/32.png) [@jzr](https://discourse.julialang.org/u/jzr)\
**Post date:** [May 10, 2021, 11:28pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/10 "2021-05-10T23:28:01Z")

</div>

Thanks. Tbh that behavior still seems incongruous with the docs which say “Test whether a vector is in sorted order.”

---

<div class="post-metadata">

**Author:** ![mkitti](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mkitti/32/12459_2.png) [@mkitti](https://discourse.julialang.org/u/mkitti)\
**Post date:** [May 11, 2021, 12:40am UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/11 "2021-05-11T00:40:27Z")

</div>

Ultimately, I think @goretkin is right that the implementation is key. Currently, the default is

```julia
if this < prev
    return false
end

```

The alternative would be as follows.

```julia
if !( this >= prev )
    return false
end

```

The second version seems less efficient since you have to do the `>=` comparison and then negate it. However, this is Julia, and we have a fancy compiler.

```julia
julia> function f(this, prev)
           if this < prev
               return false
           end
           return true
       end
f (generic function with 1 method)

julia> function g(this, prev)
           if !( this >= prev )
               return false
           end
           return true
       end
g (generic function with 1 method)

julia> f(1,2)
false

julia> g(1,2)
false

julia> f(2, 1)
true

julia> g(2,1)
true

julia> @code_llvm debuginfo=:none f(2, 1)
; Function Attrs: uwtable
define i8 @julia_f_816(i64 signext %0, i64 signext %1) #0 {
top:
  %.not = icmp sge i64 %0, %1
  %spec.select = zext i1 %.not to i8
  ret i8 %spec.select
}

julia> @code_llvm debuginfo=:none g(2, 1)
; Function Attrs: uwtable
define i8 @julia_g_818(i64 signext %0, i64 signext %1) #0 {
top:
  %.not = icmp sle i64 %1, %0
  %spec.select = zext i1 %.not to i8
  ret i8 %spec.select
}

```

Both versions compile to very similar code.

```nohighlight
julia> @code_native debuginfo=:none issorted([1, 2, 3])
        .text
        pushq %rbp
        movq %rsp, %rbp
        movq 8(%rcx), %r9
        movb $1, %al
        testq %r9, %r9
        je L57
        cmpq $1, %r9
        je L57
        movq (%rcx), %r8
        movq (%r8), %rdx
        movl $2, %ecx
L32:
        movq %rdx, %r10
        movq -8(%r8,%rcx,8), %rdx
        cmpq %r10, %rdx
        jl L55
        cmpq %r9, %rcx
        jae L57
        incq %rcx
        jmp L32
L55:
        xorl %eax, %eax
L57:
        popq %rbp
        retq
        nopl (%rax,%rax)

```

```nohighlight
julia> import Base: issorted, lt

julia> function issorted(itr, order::Base.Order.Ordering)
           y = iterate(itr)
           y === nothing && return true
           prev, state = y
           y = iterate(itr, state)
           while y !== nothing
               this, state = y
               !lt(order, prev, this) && return false
               prev = this
               y = iterate(itr, state)
           end
           return true
       end
issorted (generic function with 5 methods)

julia> @code_native debuginfo=:none issorted([1, 2, 3], lt = <= )
        .text
        pushq %rbp
        movq %rsp, %rbp
        movq 8(%rcx), %r9
        movb $1, %al
        testq %r9, %r9
        je L57
        cmpq $1, %r9
        je L57
        movq (%rcx), %r8
        movq (%r8), %rdx
        movl $2, %ecx
L32:
        movq %rdx, %r10
        movq -8(%r8,%rcx,8), %rdx
        cmpq %rdx, %r10
        jg L55
        cmpq %r9, %rcx
        jae L57
        incq %rcx
        jmp L32
L55:
        xorl %eax, %eax
L57:
        popq %rbp
        retq
        nopl (%rax,%rax)

```

Again, it looks like in practice there is not much difference for the given `lt`. Where this may make a difference is for an arbitrary `lt` that the compiler cannot easily negate.

---

<div class="post-metadata">

**Author:** ![jling](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jling/32/212909_2.png) [@jling](https://discourse.julialang.org/u/jling)\
**Post date:** [May 11, 2021, 1:59am UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/12 "2021-05-11T01:59:48Z")

</div>

> [@mkitti](#):
>
> `if !( this >= prev )`

you can’t always(?) trivially “flip it” since `lt=` can be any general binary function

---

<div class="post-metadata">

**Author:** ![tbeason](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tbeason/32/15898_2.png) [@tbeason](https://discourse.julialang.org/u/tbeason)\
**Post date:** [May 11, 2021, 2:23am UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/13 "2021-05-11T02:23:16Z")

</div>

This is an interesting find. I think the easiest way to handle this might be a new keyword, since it seems the implementation does appear to favor strict comparisons. Regardless of the outcome, I think a statement on how ties are handled belongs in the docstring.

---

<div class="post-metadata">

**Author:** ![mkitti](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mkitti/32/12459_2.png) [@mkitti](https://discourse.julialang.org/u/mkitti)\
**Post date:** [May 11, 2021, 11:26pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/14 "2021-05-11T23:26:28Z")

</div>

Ultimately, I think @goretkin is right that the implementation is key. Currently, the default is

```julia
if this < prev
    return false
end

```

The alternative would be as follows.

```julia
if !( this >= prev )
    return false
end

```

The second version seems less efficient since you have to do the `>=` comparison and then negate it. However, this is Julia, and we have a fancy compiler.

```julia
julia> function f(this, prev)
           if this < prev
               return false
           end
           return true
       end
f (generic function with 1 method)

julia> function g(this, prev)
           if !( this >= prev )
               return false
           end
           return true
       end
g (generic function with 1 method)

julia> f(1,2)
false

julia> g(1,2)
false

julia> f(2, 1)
true

julia> g(2,1)
true

julia> @code_llvm debuginfo=:none f(2, 1)
; Function Attrs: uwtable
define i8 @julia_f_816(i64 signext %0, i64 signext %1) #0 {
top:
  %.not = icmp sge i64 %0, %1
  %spec.select = zext i1 %.not to i8
  ret i8 %spec.select
}

julia> @code_llvm debuginfo=:none g(2, 1)
; Function Attrs: uwtable
define i8 @julia_g_818(i64 signext %0, i64 signext %1) #0 {
top:
  %.not = icmp sle i64 %1, %0
  %spec.select = zext i1 %.not to i8
  ret i8 %spec.select
}

```

Both versions compile to very similar code.

```nohighlight
julia> @code_native debuginfo=:none issorted([1, 2, 3])
        .text
        pushq %rbp
        movq %rsp, %rbp
        movq 8(%rcx), %r9
        movb $1, %al
        testq %r9, %r9
        je L57
        cmpq $1, %r9
        je L57
        movq (%rcx), %r8
        movq (%r8), %rdx
        movl $2, %ecx
L32:
        movq %rdx, %r10
        movq -8(%r8,%rcx,8), %rdx
        cmpq %r10, %rdx
        jl L55
        cmpq %r9, %rcx
        jae L57
        incq %rcx
        jmp L32
L55:
        xorl %eax, %eax
L57:
        popq %rbp
        retq
        nopl (%rax,%rax)

```

```nohighlight
julia> import Base: issorted, lt

julia> function issorted(itr, order::Base.Order.Ordering)
           y = iterate(itr)
           y === nothing && return true
           prev, state = y
           y = iterate(itr, state)
           while y !== nothing
               this, state = y
               !lt(order, prev, this) && return false
               prev = this
               y = iterate(itr, state)
           end
           return true
       end
issorted (generic function with 5 methods)

julia> @code_native debuginfo=:none issorted([1, 2, 3], lt = <= )
        .text
        pushq %rbp
        movq %rsp, %rbp
        movq 8(%rcx), %r9
        movb $1, %al
        testq %r9, %r9
        je L57
        cmpq $1, %r9
        je L57
        movq (%rcx), %r8
        movq (%r8), %rdx
        movl $2, %ecx
L32:
        movq %rdx, %r10
        movq -8(%r8,%rcx,8), %rdx
        cmpq %rdx, %r10
        jg L55
        cmpq %r9, %rcx
        jae L57
        incq %rcx
        jmp L32
L55:
        xorl %eax, %eax
L57:
        popq %rbp
        retq
        nopl (%rax,%rax)

```

Again, it looks like in practice there is not much difference for the given `lt`. Where this may make a difference is for an arbitrary `lt` that the compiler does not recognize.

---

<div class="post-metadata">

**Author:** ![kimikage](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kimikage/32/14534_2.png) [@kimikage](https://discourse.julialang.org/u/kimikage)\
**Post date:** [May 12, 2021, 12:06am UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/15 "2021-05-12T00:06:24Z")

</div>

BTW, it looks more natural if we use `||`.

---

<div class="post-metadata">

**Author:** ![qsong](https://avatars.discourse-cdn.com/v4/letter/q/d07c76/32.png) [@qsong](https://discourse.julialang.org/u/qsong)\
**Post date:** [May 12, 2021, 3:55am UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/16 "2021-05-12T03:55:46Z")

</div>

`issorted([a,b])` is same as `!isless(b,a)`,  
so it checks whether `[a, b]` is non-decreasing;  
OTOH, `issorted([a,b], lt=<=)` is just `isless(a,b)` and to check strictly increasing.  
The default `lt(b,a)`, not `lt(a,b)` make the situation a little confusing.

---

<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:58am UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/17 "2021-05-12T05:58:15Z")

</div>

It seems very strange to me that strict comparison, `<`, does not require “strictly increasing”.

It’s also not great that one must “look at the implementation” to understand what `issorted` does. The current docs seem to assume that the behavior is intuitively obvious. To me the behavior is profoundly weird.

---

<div class="post-metadata">

**Author:** ![ettersi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ettersi/32/6829_2.png) [@ettersi](https://discourse.julialang.org/u/ettersi)\
**Post date:** [May 12, 2021, 6:56am UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/18 "2021-05-12T06:56:08Z")

</div>

Maybe `issorted()` should have another keyword argument `strict::Bool`?

---

<div class="post-metadata">

**Author:** ![jzr](https://avatars.discourse-cdn.com/v4/letter/j/eb9ed0/32.png) [@jzr](https://discourse.julialang.org/u/jzr)\
**Post date:** [May 12, 2021, 7:01am UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/19 "2021-05-12T07:01:34Z")

</div>

> [@ettersi](#):
>
> Maybe `issorted()` should have another keyword argument `strict::Bool` ?

I don’t think so; I think it should just do the obvious thing as documented, not this weird other thing that it currently does.

---

<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, 7:24am UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/20 "2021-05-12T07:24:30Z")

</div>

We should definitely document that `lt` must define a [strict total order](https://en.wikipedia.org/wiki/Total_order#Strict_and_non-strict_total_orders). Aside from the documentation issue, it is not clear to me what behavior you would prefer:

- On one hand, you expect that `issorted(sort(A, lt=x), lt=x)` returns `true` for all `x` (which is the case if `x` defines a strict total order).
- On the other hand, you want to have a `my_lt` (either `<` or `<=`) such that `issorted(sort(A, lt=my_lt))` returns `false` when `A` contains non-unique elements.

So what should `sort(A, lt=my_lt)` do? Remove non-unique elements? It seems _very_ counterintuitive to me that `sort` would delete elements from the vector.

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