BoundsError in sort! on ill-behaved user-specified comparisons

[rened]

The following reduced example triggers a BoundsError in both 0.3.8 and latest master:

a = rand(1:5, 2, 1000)
ind = collect(1:size(a,2))
sort!(ind, lt = (x,y) -> a[1,x]<=a[1,y])

ERROR: LoadError: BoundsError: attempt to access 2x1000 Array{Int64,2}:
 2  5  5  3  5  2  2  5  5  3  4  3  2  …  3  1  1  2  5  4  1  4  5  1  4  3
 2  4  2  5  4  4  2  2  3  5  4  5  5     3  3  2  4  5  5  2  1  1  5  4  2
  at index [1,140649597000272]
 in getindex at array.jl:299
 in anonymous at /Users/rene/BTSync/code/git/sortrows/test.jl:3
 in sort! at sort.jl:297
 in sort! at sort.jl:306
 in sort! at sort.jl:359
 in include at ./boot.jl:252
 in include_from_node1 at loading.jl:133
 in process_options at ./client.jl:310
 in _start at ./client.jl:409
while loading /Users/rene/BTSync/code/git/sortrows/test.jl, in expression starting on line 3

[carnaval]

Running with --check-bounds=yes says it's a logic error in the quicksort thing.

[ViralBShah]

Cc: @StefanKarpinski @kmsquire

[malmaud]

Worth keeping in mind is the lt argument passed in this example is actually "less than or equal", which violations the algorithm's reasonable implicit assumption that if lt(x,y), then !lt(y,x).

[rened]

@malmaud great catch! this was exactly the problem, thanks a lot! it works just fine with < instead of <=.

What's the best way of helping the user here? Make the docs more explicit?

[JeffBezanson]

I'm not sure it's possible to make the algorithm robust against a comparison that's not a strict total order. We might need a separate function with bounds checks for user-defined orders.

[StefanKarpinski]

Of course, you can get the same kind of problem by sorting with isless on a user-defined type, so that doesn't solve the problem either. I feel like we may need to make this a "user beware" sort of situation.

[malmaud]

Shall we just add something to the sort! doc and close this?

[StefanKarpinski]

For now I think that's best. Do we have a label for closed issues that should maybe be revisited one day?

[KristofferC]

I but back the bug label because the exposed functionality of Julia should not crash like this from erroneous usage.

[LilithHafner]

If it's a bug, then the fix is not documenting it.