| In-place sorting with fewer moves | |
| Authors: | Jyrki Katajainen and Tomi A. Pasanen |
| Publication: | Report 98/22, Department of Computer Science, University of Copenhagen (1998), 9 app.pp. |
| Abstract: | It is shown that an array of n elements can be sorted using O(1) extra space, O(nlogn/loglogn) element moves, and n log2 n + O(nloglogn) comparisons. This is the first in-place sorting algorithm requiring o(n logn) moves in the worst case while guaranteeing O(n logn) comparisons, but due to the constant factors involved the algorithm is predominantly of theoretical interest. |
| Related: |  HTML (Journal version) |
| BibLATEX: | @report{KP1998R,
author = {Jyrki Katajainen and Tomi A. Pasanen},
title = {In-place sorting with fewer moves},
type = {Report},
number = {98/22},
institution = {Department of Computer Science, University of Copenhagen},
year = {1998},
pagetotal = {9},
}
|