| In-place sorting with fewer moves | |
| Authors: | Jyrki Katajainen and Tomi Pasanen |
| Published in: | Information Processing Letters 70,1 (1999), 31-37 |
| Full text: |  PS (219 kB) |
| DOI: | 10.1016/S0020-0190(99)00038-1 |
| Copyright: | © Elsevier Science B.V. |
| Abstract: | It is shown that an array of n elements can be sorted using O(1) extra space, O(n log n / log log n) element moves, and n log2 n + O(n log log n) comparisons. This is the first in-place sorting algorithm requiring o(n log n) moves in the worst case while guaranteeing O(n log n) comparisons, but due to the constant factors involved the algorithm is predominantly of theoretical interest. |
| Related: |  HTML (Technical report) |
| BibLATEX: | @article{KP1999J,
author = {Jyrki Katajainen and Tomi Pasanen},
title = {In-place sorting with fewer moves},
journaltitle = {Information Processing Letters},
volume = {70},
number = {1},
year = {1999},
pages = {31--37},
}
|