Sorting in linear expected time |
| |
| Authors: | M T Noga D C S Allison |
| |
| Institution: | (1) Lockheed Palo Alto Research Laboratory, 94304 Palo Alto, CA, USA;(2) Department of Computer Science, Virginia Polytechnic Institute and State University, 24061 Blacksburg, VA, USA |
| |
| Abstract: | A new sorting algorithm, Double Distributive Partitioning, is introduced and compared against Sedgewick's quicksort. It is shown that the Double Distributive Partitioning algorithm runs, for all practical purposes, inO(n) time for many distributions of keys. Furthermore, the combined number of comparisons, additions, and assignments required to sort by the new method on these distributions is always less than quicksort. |
| |
| Keywords: | Statistical sorting hybrid sorting distributive partitioning quicksort |
| 本文献已被 SpringerLink 等数据库收录！ |
|
