Efficiently insert multiple elements in a list (or another data structure) keeping their order

I have a list of items that should be inserted in a list-like data structure one after the other, and I have the indexes at which each item should be inserted. For example:

items = ['itemX', 'itemY', 'itemZ']
indexes = [0, 0, 1]

The expected result is to have a list like this: result = ['itemY', 'itemZ', 'itemX'].

I'm able to get this result with this simple approach:

result = []
for index, item in zip(indexes, items):
    result.insert(index, item)

However, this is a very slow approach once lists become huge (the complexity is O(n^2)). Is there any (relatively simple to implement) way to improve my basic approach? I guess I have to look at other data structures while I insert elements and finally transform that data structure into my result list. Are trees a good option? Insert could be done maybe in O(log(n)) (instead of O(n)), but which specific tree-like structure should I use?

Or maybe something good can be achieved by just looking at all the indexes together (instead of using them one by one).

This is probably the worst case for my slow approach (always insert items at the beginning of the list):

n = 10**6 # some large number
items = list(range(n))
indexes = [0] * n

from Recent Questions - Stack Overflow https://ift.tt/2WtY5uE
https://ift.tt/eA8V8J