Python - 262 chars * 45 / 60 = 196.5
Edit: much faster sorting algorithm.
First it will sort all the items in the list by what hundred they are in (0, 100, 200, etc), in a list in
m (note: I count these as 1 step each, so a list of 1,000,000 items will automatically have 1,000,000 steps initially)
Then it will sort the lists within
m using the bubble sorting function
This is greatly sped up from using
c on the original list to be sorted, because the amount of time it takes to sort 1000 items is small (~0.04 seconds), but exponentially increases the larger the list gets (~45 seconds at 10,000 items). But if you sort 100 lists of 100 items, it only takes .4 seconds, to sort, more than 100 times faster than sorting 1 list of 10,000 items. It should therefor take 4 seconds to sort 100,000 items, and 40 seconds to finally sort 1,000,000
In actuality, it took 45 seconds to sort the reversed 1,000,000 item list this way, and results in 50,500,000 steps:
This functon works with the given case (reverse ordered list), as well as any random case. No negative integers, though.
m=[for i in r(len(l)//100+1)];t=;o=0
for e in l:m[e//100].append(e);o+=1
for e in m:x=c(e);t+=x;o+=x
for p in r(len(l)-1,0,-1):
for i in r(p):
d=b(range(1000000)[::-1]) #reversed list
#d=b(random.sample(range(1000000),1000000)) #scrambled list
#print d # comment to not print a gigantic list
print d # number of steps
print z # time it took
Edit: by changing the amount the helper function sorts by to 100, I reduced the average time it takes to sort the list to 45 seconds. also reduces character count by 2
edit again: you know what? maybe what I'm doing isn't valid. I can change the amount the helper function sorts by to just 1 and it will sort a million items in 5 seconds.. is this valid?