ISSN:
1572-9125
Keywords:
E.5
;
F.2.2
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02017344
Permalink
