| Notes on the complexity of sorting in abstract machines | |
| Authors: | Martti Penttonen and Jyrki Katajainen |
| Published in: | BIT 25,4 (1985), 611-622 |
| Full text: |  PDF (563 kB) |
| DOI: | 10.1007/BF01936140 |
| Copyright: | © Springer |
| Abstract: | The complexity of sorting with pointer machines and successor-predecessor random access machines is studied. The size of the problem is defined as the length of the problem string. A linear time algorithm is achieved for sorting by pointer machines. For successor-predecessor random access machines linear time is sufficient in a special case. |
| Related: |  HTML (Conference paper) |
| BibLATEX: | @article{PK1985J,
author = {Martti Penttonen and Jyrki Katajainen},
title = {Notes on the complexity of sorting in abstract machines},
journaltitle = {BIT},
volume = {25},
number = {4},
year = {1985},
pages = {611--622},
}
|