**a > 0**:`y = a*x*x+b*x+c`

=> y value goes down and goes up

**a < 0**: y value goes up and goes down

A `list`

is used for insertion since it may be inserted before or after. For every entry, the right position is computed. This may sound like O(n^2) or O(nlogn). Assuming case 1 without loss of generality, the iterator (location/index finder) initially travels down and eventually travels up due to the property of the function. It consumes at most `O(2n)`

for inner and outer loop. For the final step, list data is copied into output.

```
class Solution {
public:
vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
list<int> l;
list<int>::iterator it = l.begin();
for (auto& x: nums) {
int y = a*x*x + b*x + c;
while (it != l.begin() && *it > y) it--;
while (it != l.end() && *it < y) it++;
it = l.insert(it, y);
}
return vector<int>(l.begin(), l.end());
}
};
```

The first solution is what I came up when doing the question myself. After reading other posts, I just rewrite another way of doing it. The detail explanation can be found in this link.

```
class Solution {
public:
vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
vector<int> res(nums.size()), y;
for (auto &x: nums) y.emplace_back(a*x*x+b*x+c);
int i = 0, j = nums.size()-1, k = a<0? 0: nums.size()-1;
for(; i <= j; k += a<0? 1: -1) {
if (y[i] < y[j] == a < 0) res[k] = y[i++];
else res[k] = y[j--];
}
return res;
}
};
```