caa a22 4500 465821510 CHVBK 20180323112137.0 cr unu---uuuuu 170327e19900601xx s 000 0 eng 10.1007/BF02017344 doi (NATIONALLICENCE)springer-10.1007/BF02017344 Stable in situ sorting and minimum data movement [Elektronische Daten] [J. Munro, Venkatesh Raman, Jeffrey Salowe] 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. BIT Foundations, 1990 E.5 nationallicence F.2.2 nationallicence Munro J. Department of Computer Science, University of Waterloo, N2L 3G1, Waterloo, Ontario, Canada aut Raman Venkatesh Department of Computer Science, University of Waterloo, N2L 3G1, Waterloo, Ontario, Canada aut Salowe Jeffrey Department of Computer Science, University of Virginia, 22903, Charlottesville, Virginia, USA aut BIT Kluwer Academic Publishers 30/2(1990-06-01), 220-234 0006-3835 30:2<220 1990 30 10543 https://doi.org/10.1007/BF02017344 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF02017344 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Munro J. Department of Computer Science, University of Waterloo, N2L 3G1, Waterloo, Ontario, Canada aut NATIONALLICENCE 700 1- Raman Venkatesh Department of Computer Science, University of Waterloo, N2L 3G1, Waterloo, Ontario, Canada aut NATIONALLICENCE 700 1- Salowe Jeffrey Department of Computer Science, University of Virginia, 22903, Charlottesville, Virginia, USA aut NATIONALLICENCE 773 0- BIT Kluwer Academic Publishers 30/2(1990-06-01), 220-234 0006-3835 30:2<220 1990 30 10543 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer