[bug #37130] NSArray does not implement sorting and insertion assuming sorted

[Thomas Davie]

Follow-up Comment #10, bug #37130 (project gnustep):

Sure, my point was simply that you cannot use quick sort for all sorting here,
as it is not stable, and it is possible to request a stable sort.  In my
implementation I didn't really see enormous reason to implement two separate
sorts, when one, stable one would do.

I would back up your suspicion with the fact that if you set a breakpoint in a
comparator, you will commonly see calls to mergeSort on the stack... Of
course, they could have done something nuts like name it merge sort and not
actually implement that, but it seems to suggest they did indeed use it.

Timsort would indeed be a nice choice too, and I suspect you're dead right
that you would need a bloody big threshold on the size of the split arrays for
merge sort to end up faster across multiple threads (or even gcd queues).

    _______________________________________________________

Reply to this item at:

  <http://savannah.gnu.org/bugs/?37130>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.gnu.org/