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

Question

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

Answer 1

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.

Now applying this to your problem, it can be interpreted as sorting multiple words of length 1 using counting sort. If you are sure that your string would comprise of only lowercase alphabets(or any fixed range for that matter), counting sort should work just fine for small use cases. It's easy to see that sorting a binary/ternary string would be much more efficient than sorting an alphabetical string in this case. You might want to optimise the extra space by only maintaining counts for the characters which actually occur in your string, for ex: if your string contains only 3 characters b,f,k, then you can avoid storing counts for rest of the alphabets.

As far as implementation is considered, it is language specific. You might find some way in assembly which is even more efficient. And if your input is truly very large, the likes of which can't be stored in the RAM, then you'll need to dump it on a storage device and sort it, which again is an implementation detail.