diff options
| author | Jarkko Hietaniemi <jhi@iki.fi> | 2000-08-30 22:14:13 +0000 |
|---|---|---|
| committer | Jarkko Hietaniemi <jhi@iki.fi> | 2000-08-30 22:14:13 +0000 |
| commit | be7ddd5d2d1ac50e54898aa4f400140ded3a1297 (patch) | |
| tree | 1ad3424e46e95036812b16aad2860a5bbd4d6056 /pod/perldelta.pod | |
| parent | 61e6f928c8400b55ed250dc96a4024358ab069ff (diff) | |
| download | perl-be7ddd5d2d1ac50e54898aa4f400140ded3a1297.tar.gz | |
Change the internal implementation of sort() to be mergesort
instead of quicksort, from John Linderman <jpl@research.att.com>.
Gives us better worst case, better average case, and stability.
What's there not to like? (Small fixes for threaded builds
were required).
p4raw-id: //depot/perl@6927
Diffstat (limited to 'pod/perldelta.pod')
| -rw-r--r-- | pod/perldelta.pod | 11 |
1 files changed, 11 insertions, 0 deletions
diff --git a/pod/perldelta.pod b/pod/perldelta.pod index 4e6ecea948..70d2113ed4 100644 --- a/pod/perldelta.pod +++ b/pod/perldelta.pod @@ -286,6 +286,17 @@ distribution. map() that changes the size of the list should now work faster. +=sort * + +sort() has been changed to use mergesort internally as opposed to the +earlier quicksort. For very small lists this may result in slightly +slower sorting times, but in general the speedup should be at least 20%. +Additional bonuses are that the worst case behaviour of sort() is now +better (in computer science terms it is now O(N log N), as opposed to +O(N**2) of quicksort), and that sort() is now stable (meaning that +elements with identical keys will stay ordered as they were before +the sort). + =back =head1 Installation and Configuration Improvements |