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

Here's python code for a treap with a size decoration that allows insertion at specific indexes, and reordering of whole contiguous sections. It was adapted from C++ code, Kimiyuki Onaka's solution to the Hackerrank problem, "Give Me the Order." (I cannot guarantee that this adaptation is bug free -- a copy of the original code is available in the description of this question.)

import randomclass Treap:def __init__(self, value=None):self.value = valueself.key = random.random()self.size = 1self.left = Noneself.right = Nonedef size(t):return t.size if t else 0def update(t):if t:t.size = 1 + size(t.left) + size(t.right)return tdef merge(a, b):if not a:return bif not b:return aif a.key > b.key:a.right = merge(a.right, b)return update(a)else:b.left = merge(a, b.left)return update(b)def split(t, i):if not t:return None, Noneif i <= size(t.left):u, t.left = split(t.left, i)return u, update(t)else:t.right, u = split(t.right, i - size(t.left) - 1)return update(t), udef insert(t, i, value):left, right = split(t, i)u = Treap(value)return merge(merge(left, u), right)def inorder(treap):if not treap:returnif treap.left:inorder(treap.left)print(treap.value)if treap.right:inorder(treap.right)

Output:

lst = ['itemX', 'itemY', 'itemZ']
idxs = [0, 0, 1]t = Nonefor i in range(len(lst)):t = insert(t, idxs[i], lst[i])inorder(t)"""
itemY
itemZ
itemX
"""