title: Possible to sort Array in O(n) if 99% of its elements are same?
body: <p>Asking because of interest;</p>
  
  <p>Assuming the comparison of elements in array takes O(n),
  would it be possible to sort the array in O(n) if 99% if the elements are same?</p>
  
  <p>And what if an element in the array appears more than n/2 times?
  Still O(n) possible?</p>