Time complexity of sorting binary natural numbers

Question

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.

Answer 1

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.

Answer 2

If there are N numbers, M is the number of bits in the longest number, and you have enough memory available to hold 2 copies of the data, a radix sort would be of linear order O(M×N).