creating a hash based sorting algorithm For experimental and learning purposes. I was trying to create a sorting algorithm from a hash function that gives a value biased on alphabetical sequence of the string, it then would ideally place it in the right place from that hash.

The reasoning is that theoretically if done right this algorithm can achieve O(n) speeds or nearly so. 

So here is what I have worked out in python so far:

letters = {'a':0,'b':1,'c':2,'d':3,'e':4,'f':5,'g':6,'h':7,'i':8,'j':9,
'k':10,'l':11,'m':12,'n':13,'o':14,'p':15,'q':16,'r':17,
's':18,'t':19,'u':20,'v':21,'w':22,'x':23,'y':24,'z':25,
'A':0,'B':1,'C':2,'D':3,'E':4,'F':5,'G':6,'H':7,'I':8,'J':9,
'K':10,'L':11,'M':12,'N':13,'O':14,'P':15,'Q':16,'R':17,
'S':18,'T':19,'U':20,'V':21,'W':22,'X':23,'Y':24,'Z':25}    

def sortlist(listToSort):
    listLen = len(listToSort)
    newlist = []
    for i in listToSort:
        k = letters[i[0]]
        for j in i[1:]:
            k = (k*26) + letters[j]
        norm = k/pow(26,len(i)) # get a float hash that is normalized(i think thats what     it is called)

        # 2nd part
        idx = int(norm*len(newlist)) # get a general of where it should go
        if newlist: #find the right place from idx
            if norm &lt; newlist[idx][1]:
                while norm &lt; newlist[idx][1] and idx &gt; 0: idx -= 1
                if norm &gt; newlist[idx][1]: idx += 1
            else:
                while norm &gt; newlist[idx][1] and idx &lt; (len(newlist)-1): idx += 1
                if norm &gt; newlist[idx][1]: idx += 1
        newlist.insert(idx,[i,norm])# put it in the right place with the "norm" to ref     later when sorting
    return newlist


I think that the 1st part is good, but the 2nd part needs help. so the Qs would be what would be the best way to do something like this or is it even possible to get O(n) time (or near that) out of this?

The testing I did with an 88,000 word list took prob about 5 min, 10,000 took about 30 sec it got a lot worse as the list count went up.

If this idea actually works out then I would recode it in C to get some real speed and optimizations. 

Thank for any advice that you could give.
You have reinvented a form of radix sort.
See that page for how to get rid of the two nested O(n) loops.

It is possible to get O(n) if the maximum length of the words to be sorted is assumed to be a constant.