Suppose you are given a sorted array of n distinct positive integers. Then each one is arbitrarily incremented or decremented by a value between 0 and r for some positive integer r (that is a function of n). You do not know what r is. Your task is to design a sorting algorithm that takes this perturbed array as input and returns a newly sorted version in time O(n) when r is constant (meaning it does not grow with n) and O(nlog n) time for any r (that may grow as a function of n).