Technical Reports

The ICICS/CS Reading Room


UBC CS TR-81-12 Summary

Upper Bounds for Sorting Integers on Random Access Machines, September 1981 David G. Kirkpatrick and Stefan Reisch

Two models of Random Access Machines suitable for sorting integers are presented. Our main results show that i) a RAM with addition, subtraction, multiplication, and integer division can sort $n$ integers in the range $[0,2^{cn}]$ in $O(n \log c + n)$ steps; ii) a RAM with addition, subtraction, and left and right shifts can sort any $n$ integers in linear time; iii) a RAM with addition, subtraction, and left and right shifts can sort $n$ integers in the range $[0,n^{C}]$ in $O(n \log c + n)$ steps, where all intermediate results are bounded in value by the largest input.


If you have any questions or comments regarding this page please send mail to help@cs.ubc.ca.