Upper Bounds for Sorting Integers on Random Access Machines

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.