Re: Sort function modifies the table being sorted?

[Peter Cawley <lua@...>]

On Thu, Jun 14, 2012 at 4:56 AM, Paul K <paulclinger@yahoo.com> wrote:
> I'm utterly puzzled by the behavior of this fragment:
>
> local alphanumsort = function(o)
>    table.sort(o, function(a,b)
> print('---', a, b) for k,v in ipairs(o) do print(k,v) end
>      return (o[a] or 9)..a < (o[b] or 9)..b
>    end) end
> alphanumsort({1,2,3,4,5,6,7,'a',1.2,-1})
>
> This is a simplified fragment from an application I have been working
> on. On my machine (Windows with Lua 5.1.4) it dies with:
>
> sort.pl:4: attempt to concatenate local 'b' (a nil value)
> stack traceback:
>        sort.pl:4: in function <sort.pl:2>
>        [C]: in function 'sort'
>        sort.pl:2: in function 'alphanumsort'
>        sort.pl:6: in main chunk
>        [C]: ?
>
> Where does this "nil" value come from? It is clearly not in the
> original table. if I replace ..a and ..b with tostring(a) and
> tostring(b), I get "invalid order function for sorting", which usually
> indicates that the function returns inconsistent results (1 < 5 in one
> case and 1 > 5 in another), but I don't see why it would do it in this
> case. Basically, the idea is to sort elements that match their
> positions first and sort everything else after that.
>
> Even more puzzling, when I replace "o[a] or 9" with "o[a] and 0 or 9",
> things start working as expected, but maybe it just hides the issue;
> not sure.
>
> If you review the output, you notice that some elements got swapped
> even though I would not expect them to be (that may be a red herring
> though as they get swapped in "normal" cases too). For example, values
> for 5 and 9 get swapped, even though 5 is "before" 1.2 given the
> result of the comparator.
>
> ---     -1      5
> 1       1
> 2       2
> 3       3
> 4       4
> 5       5
> 6       6
> 7       7
> 8       a
> 9       1.2
> 10      -1
> ---     2       5
> 1       1
> 2       2
> 3       3
> 4       4
> 5       1.2
> 6       6
> 7       7
> 8       a
> 9       5
> 10      -1
>
> Paul.
>

For what its worth, if you run your fragment under Lua 5.2, then you
also get the error "invalid order function for sorting". Lua 5.1 isn't
quite as rigorous in checking the comparison function, so it ends up
feeding it a nil instead.

The next question is why the order function is invalid. The stated
behaviour for the table.sort function is that the input is any array,
and the output is a sorted array. There are no statements about what
happens inbetween, or how this sorting is done. However, the reference
manual does say that the algorithm is in-place and unstable, which
should be a hint that strange things can happen. As it happens, the
current algorithm is quicksort, which involves regularly choosing
elements to be pivots and then swapping then to the end of the segment
being sorted. In this case, I'm guessing that 5 was chosen as a pivot,
and so got swapped with the end of the segment, which was 1.2. Once
the indicies of the values 1 through 7 change, your order function
starts to break down.

As has been said, the takeaway message is that table.sort is a black
box. Unsorted array goes in, said array goes through a sequence of
contortions, and then a sorted array comes out the other side. In
particular, those contortions could be anything, so your order
function shouldn't expect the array to be in any reasonable state.