# Time complexity of sorting binary natural numbers

In the comparison sort model of sorting, the fastest possible algorithm is order $$n \log(n)$$, where $$n$$ is the number of input numbers. What is the time complexity of sorting a list of natural numbers, each represented as a string of ones and zeros, and separated by commas? For example, the input $$11,1,10$$ would be sorted as $$1,10,11$$.

Here is a more precise definition of the function.

Consider the following function:

$$f:S\to S$$

where $$S$$ is the set of all finite strings over the alphabet containing three symbols, $$0$$, $$1$$ and 'comma', where $$f$$ is defined by interpreting each substring starting and ending in a comma as an integer. If such a substring starts with some zeros, ignore them. Then $$f$$ sorts these integers and returns a new string formed by representing each integer in the sorted list as a binary string and inserting commas between them. To further clarify the definition of $$f$$, here is a Python script which defines $$f$$.

def f(s):
# if the input is not a string over the alphabet "01," then return an empty output
if type(s) != str or False in [t in ['0','1',','] for t in s]: return ''
# convert the string to a list of integers and sort it
L = sorted([int(t,2) for t in s.split(',')])
# convert back to a bit string separated by commas and return this
return ','.join([f"{l:>b}" for l in L])

print(f('111,10,1,01111'))
# this outputs:
#   1,10,111,1111


Let $$n$$ denote the length of the input string, that is, the number of ones, zeros, and commas. I'd like to know the big omega time complexity of this function $$f$$ in terms of $$n$$. Please note that I do not mean to ask what the time complexity of the particular implementation of the function I defined above is, but rather the time complexity of the best possible implementation.

• What are your thoughts? Why do you think the answer would be any different for this specific way of encoding the input? What's the fastest algorithm you can come up with? If there was an algorithm to solve your problem efficiently, can you think of any cool way to use that algorithm to do something you wouldn't otherwise be able to do?
– D.W.
Sep 21, 2022 at 23:29
• You might as well ask what is the time complexity to sort numbers in unary representation, if you believe the representation affects the algorithm complexity. Sep 22, 2022 at 4:24
• The lower bounds are based on the number of comparisons required to place the elements in the right order. Knowing this, think about whether there is any difference in comparing two numbers when their representation is changed to a different base. Sep 22, 2022 at 20:57
• Quicksort does not sort require $O(n \log n)$ time (in the worst case). Sep 22, 2022 at 22:08
• Please specify whether you want a comparison sort on these binary numbers and whether you allow for restrictions on the inputs or require the binary numbers to be sorted to be general. The answer depends on these. Your question is too vague in it's current form. Sep 26, 2022 at 10:52

Assuming there are $$n$$ numbers, and each number can be represented in $$O(\log n)$$ bits, you can read in the file and each number in $$O(n \log n)$$ time, then sort with any standard comparison-based sort algorithm, for a total running time of $$O(n \log n)$$.
If each number is $$m$$ bits long, and there are $$n$$ numbers, then it can take $$O(nm)$$ time just to read in the input, so if $$m \gg \log n$$, then there is no hope for a $$O(n \log n)$$ time algorithm. In such a case, a better measure of running time is to measure the running time in terms of the length of the input. Let $$N=nm$$ be the length of the input. Then it is easy to read in the input in $$O(N)$$ time, and then sort it using a comparison-based sort in $$O(N \log N)$$ time, for a total running time of $$O(N \log N)$$ time, where $$N$$ is the length of the input.