d is the increment of i.
def sortTransformedArray(self, nums, a, b, c): nums = [x*x*a + x*b + c for x in nums] ret =  * len(nums) p1, p2 = 0, len(nums) - 1 i, d = (p1, 1) if a < 0 else (p2, -1) while p1 <= p2: if nums[p1] * -d > nums[p2] * -d: ret[i] = nums[p1] p1 += 1 else: ret[i] = nums[p2] p2 -=1 i += d return ret
@waigx Can you explain your reasoning for using d?
@waigx This is a very succinct solution. I think it should receive a lot more votes. For those who wonder what it does, here is an explanation:
If we plot the transformed array, it would form a parabola. If a > 0, the two ends will be higher than the center. So do a merge sort - move from both ends of the transformed array towards the center and if a > 0, choose the bigger element and put it at the end of the resulting array, i.e. fill the array from right to left. If a < 0, merge the elements from left to right.