Re: lhs and rhs in table.sort

[Coda Highland <chighland@...>]

On Wed, Aug 26, 2015 at 11:58 PM, Dirk Laurie <dirk.laurie@gmail.com> wrote:
> 2015-08-26 23:47 GMT+02:00 Tim Hill <drtimhill@gmail.com>:
>
>> When the sorter calls your compare function, it is asking
>> “Here are two of the items in the list you told me to sort ..
>> please tell me which one should come first in the sort?”.
>
> You can supply any function you like as long as it satisfies
> the basic rules of ordering.
>
> 1. "A must come before B" and "B must come before A"
> may not both be true (but may both be false).
> 2. If "A must come before B" and "B must come before C"
> are both true, then "C must come before A" may not also
> be true.
>
> If you function is capricious, anything can happen.
>
> 1. (Best) The sort routine detects it and give an error.
> 2. (Bad) The sort routine returns the original items in some
> meaningless order.
> 3. (Worst) The sort routine does not return at all. (I have
> been told this but never actually encountered it.)
>

3 can't happen with most sorting algorithms. Merge sort has a fixed
running time regardless of the input or the comparator. Selection sort
and insertion sort never move elements after they've been put in their
final sorted position. Quicksort can have really bad performance
characteristics in the face of a bad comparator, but its methodology
protects it from hitting an infinite loop. (I'm not sure about heap
sort.)

Bubble sort, on the other hand, is especially vulnerable to bad
comparators, because it tries to sort the entire array on every pass.
An example of a comparator that would get a bubble sort stuck in an
infinite loop is one that tries to break ties between equal elements
by comparing their positions in the array and always saying the one
with the higher index is the smaller one. (This could, for example, be
a buggy implementation of a stable-sort comparator; for a stable sort,
it should break ties by saying the one with the SMALLER index is the
smaller element.) The bubble sort would swap their positions on every
pass through the loop and therefore never reach its termination
condition.

/s/ Adam