Stable in situ sorting and minimum data movement |
| |
Authors: | J Ian Munro Venkatesh Raman Jeffrey S Salowe |
| |
Institution: | (1) Department of Computer Science, University of Waterloo, N2L 3G1 Waterloo, Ontario, Canada;(2) Department of Computer Science, University of Virginia, 22903 Charlottesville, Virginia, USA |
| |
Abstract: | In this paper, we describe an algorithm to stably sort an array ofn elements using only a linear number of data movements and constant extra space, albeit in quadratic time. It was not known previously whether such an algorithm existed. When the input contains only a constant number of distinct values, we present a sequence ofin situ stable sorting algorithms makingO(n lg(k+1)
n+kn) comparisons (lg(K) means lg iteratedk times and lg* the number of times the logarithm must be taken to give a result 0) andO(kn) data movements for any fixed valuek, culminating in one that makesO(n lg*n) comparisons and data movements. Stable versions of quicksort follow from these algorithms.Research supported by Natural Sciences and Engineering Research Council of Canada grant No.A-8237 and the Information Technology Research Centre of Ontario.Supported in part by a Research Initiation Grant from the Virginia Engineering Foundation. |
| |
Keywords: | E 5 F 2 2 |
本文献已被 SpringerLink 等数据库收录! |
|