# Is it faster to use Counting Sort to lexicographically sort characters in a word in Python?

Assuming I have very long words, is it worth it to use Counting Sort with its memory overhead to achieve linear time complexity?

I wrote a Python function that sorts the characters in a given string using Counting Sort, but it looks like I have to go through the overhead of constructing the output list and converting it to string at the end.

def count_sort(s):
counts = [0] * 26
res = []
for i, c in enumerate(s):
counts[ord(c)-97] += 1
for i, c in enumerate(counts):
for j in range(c):
res.append(chr(i+97))
return "".join(res)

# print(count_sort("noise")) -> "einos"
# print(count_sort("nuance")) -> "acennu"


I feel like this would be more efficient in programming languages with mutable strings, like C++, for example. I also wonder if it even makes sense to use if I know that words are short

• How do you test your sorts? Did you try including two strings starting with the same character? Apr 22 at 5:10
• print(count_sort("noise")) -> "einos", print(count_sort("nuance")) -> "acennu" Apr 23 at 14:03
• You are not "sorting words", you are sorting the characters of a string. Apr 23 at 14:32

Asymptotically, it doesn't matter if you have very long or short words, counting sort would take more space and time if the range in which those words lie is very large, since you will have to store counts for that range. The complexity of counting sort is $$O(n+k)$$ where $$k$$ is the range, which must be $$O(n)$$ for it to have a linear time and space complexity.