# Which is faster "Sorting strings in ascending order" or "Counting the frequency of all strings "?

I have a binary file with lots of 128 bit strings:
For Example Line 1. 1000101001000100001111001010.....
Line 2. 011010010101001001010..... and many more.
I want to sort them in ascending order, and I know that counting the frequency of all strings would be as good as sorting them (as original order does not matter).
But I don't know which is faster : sorting the file or counting the frequency of strings.
So, I want to know which option will be faster ?

• Which one do you need? Being able to count frequencies very fast is useless if you need sorted strings. So knowing which one is faster is pointless. Commented Sep 6, 2021 at 7:04

Asymptotically speaking, both tasks can be performed in time $$O(n)$$ (which is also a trivial lower bound) since there can be only finitely many distinct binary strings.
To sort the strings use radix sort where each binary string is written some base $$b$$ which is a power of $$2$$. Chose $$b$$ to be a good trade-off between the memory you need to allocate (i.e., $$\Theta(2^b)$$ words) and the number of iterations of radix sort (i.e., $$\lceil 128/b \rceil$$). You could start, e.g., with $$b=16$$. This will require linear time in the worst case.
To count the number of occurrences use an Hashmap pre-sized to a capacity $$\alpha n$$, where $$\alpha$$ depends on the load-factor of the Hashtable's implementation (the idea here is to prevent re-hasing). The keys of the hashmap are the strings, and the associated values are their number of occurrences. This will require linear time in expectation.