Julia 1.7 sort issue?

General Usage
1

I was trying to do some lexicographic sorting and came up with this “simple” code (sorry for the kinda long matrix, everything seems to work fine for the full slice):

final_pts = [0.5 0.1127016653792583 0.6116933432144834 0.5 0.5 0.9442296164361286 0.1127016653792583 0.5 0.5 0.8872983346207417 0.9802456343540101 0.5 0.5 0.5 0.18944852663138678 0.7171218746734013 0.9969159816063775 0.0030840183936224896 0.1127016653792583 0.38830665678551657 0.5 0.5 0.5 0.055770383563871484 0.01975436564598987 0.5 0.28287812532659873 0.5 0.5 0.8105514733686132 0.5 0.8872983346207417 0.8872983346207417; 0.9969159816063775 0.5 0.5 0.8105514733686132 0.28287812532659873 0.5 0.1127016653792583 0.9802456343540101 0.5 0.8872983346207417 0.5 0.9442296164361286 0.6116933432144834 0.1127016653792583 0.5 0.5 0.5 0.5 0.8872983346207417 0.5 0.0030840183936224896 0.7171218746734013 0.18944852663138678 0.5 0.5 0.8872983346207417 0.5 0.01975436564598987 0.055770383563871484 0.5 0.38830665678551657 0.5 0.1127016653792583]

function lt_slice(mat)
  function comp(i, j)
    ret = any(mat[k, i] < mat[k, j] for k in axes(mat, 1))
    @info "" i j size(mat) ret
    ret
  end
  comp
end
sort(collect(1:size(final_pts, 2)), lt=lt_slice(final_pts))

This gives an out-of-bounds exception in 1.7, an example shown below:

ERROR: BoundsError: attempt to access 2×33 Matrix{Float64} at index [1, 34]
Stacktrace:
  [1] getindex
    @ ./array.jl:862 [inlined]
  [2] #10
    @ ./none:0 [inlined]
  [3] iterate
    @ ./generator.jl:47 [inlined]
  [4] _any
    @ ./reduce.jl:1109 [inlined]
  [5] any
    @ ./reduce.jl:1105 [inlined]
  [6] any
    @ ./reduce.jl:1031 [inlined]
  [7] (::var"#comp#11"{Matrix{Float64}})(i::Int64, j::Int64)
    @ Main ./REPL[94]:3
  [8] #1
    @ ./ordering.jl:125 [inlined]
  [9] lt
    @ ./ordering.jl:112 [inlined]
 [10] partition!(v::Vector{Int64}, lo::Int64, hi::Int64, o::Base.Order.Lt{Base.Order.var"#1#3"{var"#comp#11"{Matrix{Float64}}, typeof(identity)}})
    @ Base.Sort ./sort.jl:559
 [11] sort!(v::Vector{Int64}, lo::Int64, hi::Int64, a::Base.Sort.QuickSortAlg, o::Base.Order.Lt{Base.Order.var"#1#3"{var"#comp#11"{Matrix{Float64}}, typeof(identity)}})
    @ Base.Sort ./sort.jl:575
 [12] sort!
    @ ./sort.jl:664 [inlined]
 [13] #sort!#8
    @ ./sort.jl:725 [inlined]
 [14] #sort#9
    @ ./sort.jl:772 [inlined]
 [15] top-level scope
    @ REPL[104]:1

I’ve tried it on three different machines and this behavior doesn’t happen in 1.10, but only 1.7 (and with different invalid indices). I added the @info to ensure that it’s shown my comparison doesn’t access the wrong index and it’s instead a problem with sort!.

  1. Does someone else get this behavior?
  2. Is it a problem with my code?
  3. If not, is this already known? I did a preliminary search and didn’t see anything
  4. If not, is it worth opening an issue on Julia’s github, since it’s a previous version?
2

Putting aside the error, does sortslices work for you? The default comparison is lexicographic.

julia> sortslices(final_pts, dims=2)
2×33 Matrix{Float64}:
 0.00308402  0.0197544  0.0557704  0.112702  0.112702  0.112702  …  0.887298  0.887298  0.94423  0.980246  0.996916
 0.5         0.5        0.5        0.112702  0.5       0.887298     0.5       0.887298  0.5      0.5       0.5
3

Unfortunately, not; I need the permutation to sort both the matrix and an associated vector with length size(final_pts,2) (otherwise, sortslices would be great!).

4

Probably no - 1.10 will be the LTS version very shortly, and 1.7 was never an LTS version anyway, so there won’t be a 1.7.4 release that would fix this issue if it really is one.

1 Like
5

I guess I should’ve tested it on other versions, but I assume this got fixed when they changed the base sorting algorithm in 1.9, because I just checked and it doesn’t work using the default algorithms in 1.6, 1.7, 1.8, but works in 1.9, 1.10.

On the other hand, if I use alg=Base.InsertionSort in <1.9, it works. If I use alg=Base.QuickSort in >=1.9, it no longer works, so I think that this is a quicksort issue in previous non-LTS versions?

Given this research, I’ll probably open an issue since it’s no longer just an older non-LTS version.

EDIT: Adding that a simple thought process leads me to realize this is a problem with unstable lexicographic sorting. As suggested here, in >1.9 you can do sortperm(eachcol(matrix)) and before that you can just do sortperm(collect(eachcol(matrix)))

6

Technically this is a bug in Julia 1.6 LTS as well, which is still LTS until Julia 1.11 is actually released.