title: Memory and time-efficient sorting of all rotations of a long array
body: <p>I am looking for a memory and time-efficient solution to the below problem. It is easy to think of a basic algorithm that uses O(n<sup>2</sup>) memory and O(n<sup>2</sup> log n) time (?), and I would like to know if there is an algorithm that is significantly more memory and time-efficient (for certain input structures).</p>
  
  <p><strong>Input</strong>: Array a of length n populated with nonnegative integers. Each integer in the array is of magnitude less than or equal to b. I am interested in settings where n is large (tens of millions) and b is relatively small compared to n (hundreds). We can assume that the number of occurrences of any particular integer in a is bounded above by m, where m is on the order of n/b.</p>
  
  <p>Consider the set of all rotations of the array a, i.e., if a = (a<sub>1</sub>, a<sub>2</sub>, ..., a<sub>n</sub>), then its rotations are (a<sub>1</sub>, a<sub>2</sub>, ..., a<sub>n</sub>), (a<sub>2</sub>, a<sub>3</sub>, ..., a<sub>n</sub>, a<sub>1</sub>), (a<sub>3</sub>, a<sub>4</sub>, ..., a<sub>n</sub>, a<sub>1</sub>, a<sub>2</sub>), ..., (a<sub>n</sub>, a<sub>1</sub>, a<sub>2</sub>, ..., a<sub>n-1</sub>). Let r<sub>1</sub>, r<sub>2</sub>, ..., r<sub>n</sub> denote the lexicographically sorted (increasing) ordering of the rotations of array a (using 0 &lt; 1 &lt; 2 &lt; ... &lt; b).</p>
  
  <p><strong>Output</strong>: Two arrays <em>first</em> and <em>last</em> that store the first and last elements of r<sub>1</sub>, r<sub>2</sub>, ..., r<sub>n</sub> according to the sorted order.</p>
  
  <p><strong>Basic algorithm</strong> (not memory or time-efficient): Construct all rotations of a and store them in a matrix A (which uses O(n<sup>2</sup>) memory). Define a sorting routine (which uses a standard sorting technique) to sort A. Extract the first and last columns of the sorted matrix. Presumably the best time complexity of the sorting step is O(n<sup>2</sup> log n), i.e., O(n log n) for the sorting algorithm multiplied by O(n) for each pairwise comparison.</p>
  
  <p><strong>Second algorithm</strong>: We can walk through the array and store the positions in it that start with any integer i less than or equal to b (this is an O(n) time and O(nm) memory operation). Then, we can generate all rotations starting with a particular integer i and sort this matrix of rotations as per the basic algorithm (storing this matrix uses O(nm) memory and sorting presumably takes O(mn log m) time). It is easy to construct the output by repeating the process for every integer i from 0 to b.</p>
  
  <p>Is there an approach that is more memory-efficient that uses a tailored sorting strategy? I am hopeful because storing the output only needs O(n) memory.</p>