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 _______________________________________________ mc-devel mailing list https://mail.gnome.org/mailman/listinfo/mc-devel