import random from exceptions import ValueError def indirectInsertion(F, ordering, x): """ Inserts x in F array ordered indirectly by ordering. """ L = len(ordering) #Perform check, if L != len(F): raise ValueError k = L-1 save = ordering[k] # index to space for x while k >= 0 and x < F[ordering[k]]: ordering[k] = ordering[k-1] k -= 1 k = min(L-1, k+1) # print "position to insert x", k ordering[k] = save F[save] = x ordering[k] = save if __name__ == "__main__": #Example. #Create random data array. F = [random.random() for i in range(10)] #Decorate, sort, undecorate G = [(f, i) for i, f in enumerate(F)] G.sort() ordering = [g[1] for g in G] print "Original data" for i in range(len(F)): print i, ordering[i], F[ordering[i]] #Generate x to insert indirectly in array F. x = random.random() print "x to insert=", x indirectInsertion(F, ordering, x) for i in range(len(F)): print i, ordering[i], F[ordering[i]] When the program runs, it outputs Original data 0 6 0.0495661645612 1 7 0.0716388504517 2 0 0.181165380138 3 3 0.193601438133 4 8 0.370737951412 5 1 0.409117107263 6 9 0.544771417861 7 5 0.640157511435 8 4 0.831191183469 9 2 0.861514272553 x to insert= 0.463842630209 0 6 0.0495661645612 1 7 0.0716388504517 2 0 0.181165380138 3 3 0.193601438133 4 8 0.370737951412 5 1 0.409117107263 6 2 0.463842630209 7 9 0.544771417861 8 5 0.640157511435 9 4 0.831191183469