lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

2013/5/9 Eike Decker <>:

>>> 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.