On Wed, Oct 24, 2018 at 8:03 PM Huw Davies huw@codeweavers.com wrote:
I don't think this is an issue. Let's just use qsort for now and if it turns out to be needed you can roll your own sort later on.
The idea is to make things easy to review, that way you'll stand much more chance of getting your patches in.
Huw.
Well honestly, this would already be an issue for me (as a user, in usability) if I used this on a non-merge-sort qsort system that doesn't use glibc, I can imagine there's surely other people with my use cases...
I'm talking mostly about performance here, not even the stability of the sort (merge sort minimizes the amount of comparisons, so it's *much* faster in this situation than for example quicksort, since that's the bottleneck). Most of those large lists also have very long prefixes that expand (e.g. foo\bar\baz\bla\x\y\z...) so that compounds the performance problem (string comparisons).
Yeah, it's probably best to start with a qsort to simplify the patch for now, but I still think a merge sort should definitely be used eventually in a later patch, just for consistency on all platforms instead of it being sluggish on those not using merge sort (e.g. taking 2 seconds instead of 1 second is a large difference).