There are a lot of brilliant answers out there. But I noticed that many of them using vector to store the output. However, as stated in official documentation of C++, ** "Compared to other base standard sequence containers (array, vector and deque), lists perform generally better in inserting, extracting and moving elements"**. Therefore, we should use a list to store the output that are generated by our algorithm and create the ultimate solution using the list. For example, we have a beautiful solution below:

```
vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
sort(people.begin(), people.end(),[](pair<int,int> p1, pair<int,int> p2){
return p1.first > p2.first || (p1.first == p2.first && p1.second < p2.second);
});
vector<pair<int,int>> sol;
for (auto person : people){
sol.insert(sol.begin() + person.second, person);
}
return sol;
}
```

This solution runs in 76 ms.

However, if we use a list as a temporary container. We can reduce the running time to 46 ms, which beats a lot of solutions.

```
vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
sort(people.begin(), people.end(),[](pair<int,int> p1, pair<int,int> p2){
return p1.first > p2.first || (p1.first == p2.first && p1.second < p2.second);
});
list<pair<int,int>> sol;
for (auto person : people){
auto iter = sol.begin();
advance(iter, person.second);
sol.insert(iter, person);
}
return vector<pair<int, int>>(sol.begin(), sol.end());
}
```

**BTW**, I want to explicitly state that the worst case time complexity of the latter algorithm is still **O(n^2)**. Even if sorting takes O(nlogn), the second procedure still takes O(n^2). Because the iterator of list container is *not random access iterator*, so the time complexity of "advance()" is linear time, and that's why we cannot do like this "sol.begin() + person.second". List-based solution is better than vector-based solution, because there are a lot of moving operations (when inserting element) in the latter.