1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72  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 = L1
save = ordering[k] # index to space for x
while k >= 0 and x < F[ordering[k]]:
ordering[k] = ordering[k1]
k = 1
k = min(L1, 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

I think you have a lot to learn about Python. Fundamentally, your "solution" is a bad idea, and I hope nobody (including yourself) uses it. I think you have a lot to learn about Python.
Python lists don't store the data itself, they store references. Integers are stored in Python as immutable objects. So your array of ints is really an array of references, just as your array of large data blobs is also an array of references. In other words: you are copying exactly the same amount of data when maintaining a sorted array of integers as you would maintaining a sorted array of large objects. So there is absolutely no point in maintaining this external "ordering" array.
Second, it is much faster to use Python facilities to do what needs doing than to laboriously write it out yourself. To insert an item in sorted order, you should at least use the "insert" method on an array to insert it into the correct place, rather than manually making room in the array as you have done. (More on this in a moment.)
Third, the sorting algorithms in Python are fantastically fast, and optimized (among other things) for sorting alreadymostlysorted lists. They cannot help but beat your awful O(n) search, which is so bad I wonder a little if you aren't trolling. So even adding the item to the end of the list, then calling sorted() on it, would be faster than what you've done.
Finally, with Python "the batteries are included"; Python comes with libraries to do many common tasks, including maintaining sorted arrays. Your entire recipe canand shouldbe replaced with:
/larry/
p.s. instead of "for i in range(len(F))", try "for i, object in enumerate(F)".
I have to maintain more than one list ordered in my application.The F list may represent energy and another list may be cluster atom coordinates. I prefer the lists separate for ease of programming.