If we consider literature, sorting algorithms are based only on number of comparisons needed to sort a list of size n, considering that n is the size of the input.But if we want to encode input, we can't encode each object of the list into a fixed-size binary representation because hence, we would consider that the domain of the objects is fixed and thus, I think we could find better sorting algorithms by precomputing some stuff in the Turing Machine.If we consider that the domain isn't fixed, we have to encode each of our items into a $\log(n)$-size representation. Thus the input is of size $N = n\log(n)$. But as our numbers are of variable length, then we can consider that comparison has a cost of $\log(n)$, but even with this, if we apply a reasonable sorting algorithm (ie an $n \log n$ algorithm), the algorithm will take $n \log^2(n)$ time in a Turing machine, where $n$ is the number of objects, but where $n \log n$ is the size of our input. In this case, we have an algorithm of complexity lower than $O(N \log(N))$ where $N$ is the size of the input.Is there a mistake?
Sorting algorithm with a complexity smaller than $n \log n$?
cc.complexity theory;ds.algorithms;sorting
Without looking at any details, why do your say your algorithm beats $O(N\log N)$?In your notation, $N\log N = n\log n\log(n\log n) = n\log n\log n + n\log n\log\log n = O(n\log^2n)$.No contradiction.