algorithm - Is it possible to write generic bucket sort? -

algorithm - Is it possible to write generic bucket sort? -

as know, bucket sort algorythm efficient: running time around o(n + m), n number of items sorted, , m size of array utilize fpr sorting. problem is suitable limited set of keys: integers, fill size of our array.

the question: there ways utilize arbitrary type of key?

for example, if have arbitrary key, can utilize hashcode bucket index. of course, need preserve rule: if key1 > key2 hashcode1 > hashcode2 etc

is possible implement this?

for example, if need sort strings, easy obtain bucket indexes of strings built character representations.

the runtime you're giving - o(n + m) - , fact you're saying algorithm works integers makes me think you're referring counting sort rather bucket sort. if you're curious whether it's possible find way give objects arbitrary indices hash codes such can counting sorted, reply no, it's not possible this.

take strings, example. suppose have mapping strings integers such if str1 < str2, code(str1) < code(str2). now, take strings "" , "b" , determine code("") , code("b"). know code("") < code("b"). now, define

k = code("b") - code("") - 1

this number of integers between code("") , code("b"), exclusive.

next, think strings "a", "aa", "aaa", "aaaa", etc. until have k + 1 of them. notice that

"" < "a" < "aa" < "aaa" < "aaaa" < "aaaaa" < ... < "b".

this means should have

code("") < code("a") < code("aa") < code("aaa") < code("aaaa") < ... < code("b")

here's problem: there k distinct integer values between code("") , code("b"), there k+1 strings need fill in gaps. forcefulness 2 strings collide , have same numeric code, causing sort fail.

the reason problem integers not have same order type many other structures, such strings, pairs of integers, real numbers, etc.

algorithm sorting bucket-sort