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

[Niels Grewe]

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

Well, actually, the documentation states that sorting is only required to be
stable if you actually request it (though Apple might actually always do
stable sorting and just doesn't want to make any guarantees for the general
case, I didn't check.) 

As far as the choice of sort algorithm is concerned, I highly suspect that
Apple has actually implemented their sorting stuff with mergesort, because it
is inherently easy to do it in parallel and they seem to like that :-) (by the
way: while Thomas' mergesort implementation is stable, you can also do
mergesort in an unstable way, depending on how you slice the array).

Another alternative that we could consider is timsort, which is the default
sorting algorithm in Python, Android and Java 7 and is said to be marvellously
fast for partially pre-sorted inputs as they occur in real-world settings. It
is stable, but I didn't see any obvious avenues for parallel execution.
(Anyways, I suspect that you'd need to throw a lot of cores at a parallel
mergesort to beat timsort in something other than a contrived
micro-benchmark).

(Actually, you can read that as an endorsement that I might consider it a fun
project to implement timsort in -base…)

Cheers,

Niels 


    _______________________________________________________

Reply to this item at:

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

_______________________________________________
  Nachricht gesendet von/durch Savannah
  http://savannah.gnu.org/