Based on this solution which I first saw brought up by @bigoffer4all **here** (and which I **explained here**):

```
def reconstructQueue(self, people):
queue = []
for p in sorted(people, key=lambda (h, t): (-h, t)):
queue.insert(p[1], p)
return queue
```

That takes O(n^2) because each `insert`

into the list takes O(n).

Instead of just one long list of all people, I break the queue into O(sqrt(n)) blocks of size up to sqrt(n). Then to insert at the desired index, I find the appropriate block, insert the person into that block, and potentially have to break the block into two. Each of those things takes O(sqrt(n)) time.

```
def reconstructQueue(self, people):
blocks = [[]]
for p in sorted(people, key=lambda (h, t): (-h, t)):
index = p[1]
for i, block in enumerate(blocks):
m = len(block)
if index <= m:
break
index -= m
block.insert(index, p)
if m * m > len(people):
blocks.insert(i + 1, block[m/2:])
del block[m/2:]
return [p for block in blocks for p in block]
```

"Unfortunately", Python's `list.insert`

is really fast compared to doing things in Python myself, and with the inputs allowed here (less than 1100 people), the O(n^2) solution wins. Locally I tested with larger inputs, and around 200000 people the two solutions were about equally fast. With 300000 people, the O(n sqrt(n)) solution was about factor 1.25 faster, and with a million people, the O(n sqrt(n)) solution was about factor 2.2 faster

The testing code:

```
# The original O(n^2) solution.
class Solution(object):
def reconstructQueue(self, people):
queue = []
for p in sorted(people, key=lambda (h, t): (-h, t)):
queue.insert(p[1], p)
return queue
nsquared = Solution().reconstructQueue
# The O(n sqrt(n)) solution.
class Solution(object):
def reconstructQueue(self, people):
blocks = [[]]
for p in sorted(people, key=lambda (h, t): (-h, t)):
index = p[1]
for i, block in enumerate(blocks):
m = len(block)
if index <= m:
break
index -= m
block.insert(index, p)
if m * m > len(people):
blocks.insert(i + 1, block[m/2:])
del block[m/2:]
return [p for block in blocks for p in block]
nsqrtn = Solution().reconstructQueue
# Generate a large test case and time it.
from bisect import bisect
from random import randint, shuffle
from timeit import timeit
n = 300000
heights = [randint(1, n) for _ in range(n)]
standing = []
people = []
for h in heights:
i = bisect(standing, -h)
standing.insert(i, -h)
people.append([h, i])
shuffle(people)
for solution in nsquared, nsqrtn, nsquared, nsqrtn:
print timeit(lambda: solution(people), number=1)
```