Improved nonconservative sequential and parallel integer sorting

We consider the problem of deterministic integer sorting on unit-cost sequential and parallel machines with a large word length and show that n integers drawn from {0,...,m-1} can be sorted using a word length of O(m log n) bits either in O(n) time on a unit-cost RAM or in O(log n) time on a unit-cost EREW PRAM with O(n/log n) processors. Spending O(log log log m) additional sequential or parallel time, we can reduce the necessary word length to O(min}n log n log m + (log m)^1+ε{lunate}, m^ε{lunate}+log n}) bits, for any fixed ε{lunate}>0. Previous algorithms with a linear time-processor count either cannot so arbitrary integers or require a much larger word length.