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 =  * 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