Re: Sort function modifies the table being sorted?

[Paul K <paulclinger@...>]

Thanks to all who commented on this; it is indeed a flaw in my logic
as it was based on an incorrect assumption that correctly "positioned"
elements in the array won't move. As many of you noted, quicksort will
swap elements as part of its processing (auxsort in ltablib.c), which
will cause `o[a] or 9` logic to break: when 5 is compared with 3 it
will return `true` one time and `false` another when the fifth element
changes its value to 1.2.

It seems like 5.2 made some improvements to the algorithm to
(correctly) report invalid sort function rather than to create a nil.

Adding `and 0` makes it stable, which fixes the issue. So, it's not so
much that I can't access the table being sorted (my reading of the
code for auxsort didn't reveal any pitfalls related to that), but
rather you can't expect that table values have not been modified
during sorting. In this case I only need to check for presence of an
index, so it should work correctly.

Paul.

On Thu, Jun 14, 2012 at 3:23 AM, Peter Cawley <lua@corsix.org> wrote:
>
> 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.
>