title: Find an algorithm to sort an array given its status after sorting
body: <blockquote>
  <p>Let <em>A</em> be an array with <em>n</em> elements. <em>A</em> is not sorted, nonetheless, after sorting the array, the difference between any two adjacent elements would be either <em>k<sub>1</sub>, k<sub>2</sub> or k<sub>3</sub></em>.</p>
  <p><strong>It should be noted that <em>k<sub>1</sub>, k<sub>2</sub> and k<sub>3</sub></em> are not given, and all of them are <em>natural!</em></strong></p>
  <p>For example, given the array:</p>
  <pre><code>A = { 25, 7, 5, 9, 32, 23, 14, 21}
  </code></pre>
  <p>After sorting the array, we would get -</p>
  <pre><code>A = { 5, 7, 9, 14, 21, 23, 25, 32}
  </code></pre>
  <p>The difference between the first pair (5, 7) is 2; so <em>k<sub>1</sub></em>=2, the difference between the third pair (9,14) is 5, so <em>k<sub>2</sub></em>=5, whereas the difference between the fourth pair (14, 21) is 7, so <em>k<sub>3</sub></em>=7. The difference between other adjacent pairs is also 2, 5 and 7.</p>
  <p>The algorithm for sorting the array should be as best as possible (obviously below <em>O(nlogn)</em>).</p>
  </blockquote>
  <p>I managed to answer a similar question where the difference between any two adjacent elements was either <em>k, 2k or 3k</em>, where <em>k</em> is real. But I couldn't find an appropriate algorithm following a similar method, by finding <em>k</em>, dividing by it and doing bucket sort.</p>
  <p>By finding the minimum and second minimum we can find one of the <em>k</em>'s. But <em>k</em> could be <em>n<sup>2</sup></em> — so finding the maximum does not help either... I am really lost!</p>
  <p><strong>Disclaimer:</strong> This question has been asked before, but no answer was given to the problem, and the question was not easy to understand.</p>