[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[bug #37130] NSArray does not implement sorting and insertion assuming s
From: |
Niels Grewe |
Subject: |
[bug #37130] NSArray does not implement sorting and insertion assuming sorted |
Date: |
Wed, 12 Sep 2012 12:54:40 +0000 |
User-agent: |
Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.8 (KHTML, like Gecko) Chrome/23.0.1246.0 Safari/537.8 |
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/