Stable in situ sorting and minimum data movement

Autor:	J. I. Munro, Venkatesh Raman, J. S. Salowe
Rok vydání:	1990
Předmět:	In situ Sorting algorithm Logarithm Computer Networks and Communications Applied Mathematics Combinatorics Computational Mathematics sort Algorithm Time complexity Software Quicksort Linear number Mathematics
Zdroj:	BIT. 30:220-234
ISSN:	1572-9125 0006-3835
DOI:	10.1007/bf02017344
Popis:	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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::9b0d59757a1a627065eb37133e75cb9a https://doi.org/10.1007/bf02017344 Zobrazit plný text záznamu Full text from SpringerLink