Sorting algorithm

[Andrei Alexandrescu]

On 10/8/11 10:36 AM, Xinok wrote:
> On 10/8/2011 11:04 AM, Andrei Alexandrescu wrote:
>> On 10/08/11 10:01, Xinok wrote:
>>> On 10/8/2011 9:15 AM, Andrei Alexandrescu wrote:
>>>> On 10/07/11 23:00, Xinok wrote:
>>>>> Thanks, I'll look into it when I have a little more time.
>>>>
>>>> Looking forward to it.
>>>>
>>>>> If my algorithm were to be implemented in Phobos, the template
>>>>> arguments
>>>>> for std.algorithm.sort would need to be modified. For my algorithm
>>>>> to be
>>>>> stable, it requires defining two conditions, both a 'less' and
>>>>> 'greater'.
>>>>
>>>> Wouldn't swapping the argument to less work?
>>>>
>>>>
>>>> Andrei
>>>
>>> The merge step in my algorithm is similar to Timsort, in that it can
>>> merge left to right as well as right to left. This needs two conditions
>>> to do a stable sort, 'less or equal' and 'greater or equal'.
>>>
>>> By swapping the arguments, you can only get 'greater or equal'. You're
>>> still missing 'less or equal', which is required for my algorithm to be
>>> stable.
>>
>> I don't understand. Say all you have is "<". Then you can do everything:
>>
>> a <= b is !(b < a)
>> a > b is b < a
>>
>> This is an absolute classic. Probably it's negation that is missing from
>> your assumptions? You can always negate a predicate.
>>
>>
>> Andrei
>
> I actually wasn't aware you could do that O.o, although you got the
> operators wrong in your example.

Where?

> It does add overhead though. It requires two comparisons, and possibly
> twice the number of lookups, such as in this statement:
> lef[c] > rig[off - c]

That's rig[off - c] < lef[c].

> How about, if the greater argument is empty, then it fills it
> automatically with this. But also give the programmer the option to
> define both conditions for more efficient code.

I think I'm missing something. Again: if you have "<" then "<=", ">", 
and ">=" are zero cost.

What is more expensive is deciding a == b. You need to do it by saying 
!(a < b) && !(b < a). That's a cost worth paying because the second 
expression is more general - it allows you to define equivalence classes 
by using "<" even though the objects are not equal.


Andrei