Re: Buggy sort

["Yury V. Zaytsev" <yury shurup com>]

On Tue, 2015-06-30 at 00:46 +0300, Nicolas Rybkin wrote:
> But maybe anyone has any ideas? This issue is really important to me.

Nicolas,

Wow, hats off for the discovery and analysis. Could you please specify
on which platform you are running mc, which C library are you using,
etc.?

As you saw, the "unsorted" order has been implemented by passing a sort
routine that simply compares equal for all elements to qsort.

However, quicksort by definition is not a *stable* sorting algorithm,
which means that there is no guarantee that the order of the elements is
preserved if all elements compare equal for efficient implementations of
qsort. That is, in theory, qsort is allowed to return some permutation
of elements if they compare equal, like in our case, and certainly can
swap first and last elements if they are equal at will.

Of course, in practice, quicksort is often implemented to be "mostly
stable" such that this kind of random shuffling is not happening on
purpose when it's not absolutely required for performance.

Therefore, frankly speaking, I'm very baffled by your post. It seems
that you were able to find a platform that implements quicksort so
efficiently as to make it unstable for some lists, and also found some
file lists that trigger the re-ordering...

...unless your analysis is incorrect and a problem is in reality
somewhere else :-)

So, it would be great if you'd post some more details (see above,
platform, libc and list of files), so that I and/or Andrew can possibly
reproduce it. The best way would be to marshal the list of file_entry_t
to a file and make sure this qsort issue happens outside of mc, but I
understand that this could be too much work for you...

The number one question here for me would be, could it be some
off-by-one bug, as in are all other sorts working correctly on these
directories in all cases, and my theory above is correct?

-- 
Sincerely yours,
Yury V. Zaytsev