title: Sorting array A in o(nlogn)
body: <p>Given array A of integers of length n. sort A in (small o) o(nlogn) when in the sorted array A ,every two consecutive elements differ by either k1,k2,k3 where k1,k2,k3</p>
  
  <p>are different natural numbers.</p>
  
  <p>I am having a problem solving this question, i tried finding the minimum on A
  and making three new arrays each starts with min{A} of length n, forming a arithmetic sequence in each array using k1,k2,k3. merging the results and removing duplicated copies of each element and finally cutting all elements after max{A} in the new sorted array of length 3n. all operations are O(n)</p>
  
  <p>.</p>
  
  <p>the problem is this doesn't work when the difference between max{A}−min{A}
  is not divisible by any k1,k2,k3</p>
  
  <p>.</p>
  
  <p>any help or insight would be greatly appreciated. </p>