Linear time algorithm for array with distinct element
You cannot do it in linear time using only comparisons. If you could, then you could do it for the array and its reverse in $O(n)$ and then for each element determine in $O(1)$ its position in the sorting of the array. This gives a comparison-based linear time sorting algorithm, which we know cannot exist.

You have to tell us more about the domain of the elements in the input array if you want to get an $o(n \log n)$ algorithm. For example, do you have a constant upper bound on the value of the maximum element?