3
$\begingroup$

Suppose we want to sort an array that contains $n$ different integers in the range $[1,2n]$. It is known that this requires $\Theta(n\log n)$ comparisons. But comparing integers which might be as large as $n$ might requires time $\Theta(\log n)$ since we have to compare them bitwise. So, apparently the runtime complexity of sorting is $\Theta(n\log^2 n)$. Is this correct? If so, why is it taught that the complexity of sorting is $\Theta(n\log n)$? Is there a better algorithm for sorting which runs in time $\Theta(n\log n)$?

EDIT: I understand that the question depends on the computational model. In fact, I just found an interesting unanswered question that specifically asks about the runtime complexity of sorting on a Turing machine. Originally, I had in mind a realistic computer, only with unlimited memory. In such a computer, we can represent arbitrarily large integers (as sequences of bytes). We are given an array that contains $n$ different integers, each of which is between $1$ and $2n$. We measure the clock-time it takes to sort this array, as a function of $n$. What function will we see?

$\endgroup$
  • 2
    $\begingroup$ What is your model of computation? Is it RAM model? $\endgroup$ – aaag Mar 8 '17 at 13:38
  • $\begingroup$ See en.wikipedia.org/wiki/… $\endgroup$ – paparazzo Mar 8 '17 at 14:34
  • 2
    $\begingroup$ Your $n$ is not your problem's input length, and in fact, $\Theta \hspace{-0.05 in}\left(\hspace{-0.03 in}n\hspace{-0.04 in}\cdot \hspace{-0.04 in}(\hspace{.02 in}\log(n))^{\hspace{.02 in}2}\hspace{-0.04 in}\right) \: = \: \Theta \hspace{-0.03 in}\left(\text{input_length}\hspace{-0.03 in}\cdot \hspace{-0.03 in}\log(\text{input_length})\right) \;\;\;$. $\;\;\;\;\;\;\;\;$ $\endgroup$ – user12859 Mar 8 '17 at 15:00
6
$\begingroup$

Algorithms are usually analyzed using the random access machine model. In this model, arithmetic operations on machine words take time $O(1)$. A machine word contains $O(\log n)$ bits, where $n$ is some natural parameter, say the length of the input (in machine words!).

Given this definition, comparison-based sorting algorithms run in time $O(n\log n)$ as long as the arguments fit in a constant number of machine words.

Sorting algorithms probably take more than $n\log^2 n$ time on a Turing machine, since Turing machines have no random access. Turing machines are not so interesting, however, for analyzing the running time of algorithms, except for special circumstances such as proving results on the Turing machine model itself.

In your particular case, you can actually sort the array in $O(n)$ using counting sort. The $\Omega(n\log n)$ lower bound only holds for some models such as the comparison model.

$\endgroup$
  • $\begingroup$ I think counting sort would be O(2n) $\endgroup$ – paparazzo Mar 8 '17 at 17:50
  • 1
    $\begingroup$ @Paparazzi ... which is the same as $O(n)$. $\endgroup$ – Yuval Filmus Mar 8 '17 at 18:11
3
$\begingroup$

The correct statement is that any comparison-based sorting algorithm will require $\Theta(n\log n)$ comparisons in the worst case. How long each comparison will take depends on what you're sorting and what model of computation you're using.

$\endgroup$
  • $\begingroup$ Would the down-voter care to explain? $\endgroup$ – David Richerby Mar 9 '17 at 12:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.