Possible Duplicate:
Interview Q: sorting an almost sorted array (elements misplaced by no more than k)
I have a partially sorted array with the property that every element is within d units of its properly sorted position. I am wondering if there is a way to sort this array -- by exploiting this fact -- in less than n log n time.