Sorting algorithm

[Andrei Alexandrescu]

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