Re: A stable sort

[Dirk Laurie <dirk.laurie@...>]

2013/5/9 Eike Decker <zet23t@googlemail.com>:

>>> I think a native C implementation would be pretty straight forward
>>> and fast.
>
>> As a starting point, you're welcome to adapt my C implementation
>> of Fisher's version in any way you like.
>
> I still lack a C development environment on my new machine :(
>

I have simply used your strategy with my C merge subroutine, and
it's a little slower than my implementation of Fisher's strategy.
That is to be expected, since that routine does not call anything
smaller than 12. I'll experiment with doing say 8-element or
16-element bins with insert sort.

> Understandable - I wonder if there could be a trick though to maintain
> inplace, but probably, there isn't, unless computational runtime is
> suffering.

The Wikipedia merge sort article is quite thorough.

> due to the relatively cheap check if the arrays are sorted,

That will work even better with an in-place merge.