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.gif>PDF (563 kB)  
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.gif>HTML (Conference paper)  
  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},
This page was generated by Jyrki Katajainen <> on 31.12.2011.