4
$\begingroup$

Is $Ω(n\log n)$ the lower-bound for all sorting algorithms or just comparison-based sorting algorithms?

If the latter, is it possible for there to be general-purpose sorting algorithms which perform better than $Ω(n\log n)$?

General-purpose, for example, means you aren't assuming elements have a fixed number of bits.

The input to the algorithm is a sequence of $n$ bits. The bits are an encoding of integers.

Improve this question
$\endgroup$

4 Answers 4

Reset to default
4
$\begingroup$

Integers can be sorted in $o(n\log n)$ time, depending on your exact computation model – see Wikipedia. Going in the other direction, the $\Omega(n\log n)$ lower bound also holds for algebraic decision trees (so for example, comparing sums of elements doesn't enable you to get an $o(n\log n)$ algorithm). See for example Erickson's Lower bounds for external algebraic decision trees, which considers an even more general model.

As a further comment, if all you are assuming about your elements is that they are comparable, then all you can do is compare them, and so you get comparison-based sorting. In that sense your question isn't really well-defined, since you are not explaining which operations on your elements are legal.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the answer! I added clarification to my question; hopefully it is closer to well-defined. Although your first sentence answers it (I had to lookup Small O as I forgot). $\endgroup$
    – Jesus is Lord
    Commented Nov 26, 2017 at 23:46
5
$\begingroup$

O($n$ $log$ $n$) lower bound complexity assumes the length of each key bit is constant. If not, then in the worst case you must compare nearly all bits, and multiply the complexity by that length and get O($kn$ $log$ $n$)

In contrast, some non comparison sorts with arbitrary key lengths can be done in worst case O($kn$).

EDIT: To add more detail:

For Counting Sort, the worst case and average case are O($n+r$) where $r$ is the range of keys (max - min).

For LSD Radix sort the worst case and average case are O($n+k/d$) where $k$ is the key length and $d$ is the digit size.

You mention that there is no limit on key bit length. It would seem that LDS Radix has better worst case performance: $O(k(n+ln\ n))$ > $O(n+k/d$), putting aside other factors such as space.

Improve this answer
$\endgroup$
11
  • $\begingroup$ In terms of $n$ (i.e. when $r$, $k$, and $d$ are as large as possible/approach $n$), what is the worst case run-time for Counting Sort and LSD Radix sort? $\endgroup$
    – Jesus is Lord
    Commented Nov 28, 2017 at 1:35
  • $\begingroup$ For Counting Sort, the worst case and average case are O(n+r) where r is the range of keys (max - min). For LSD Radix sort the worst case and average case are O(n+k/d) where k is the key length and d is the digit size. (As stated in the answer). Check the tables of worst/average run times given in en.wikipedia.org/wiki/Sorting_algorithm. $\endgroup$
    – Craig Hicks
    Commented Nov 28, 2017 at 2:13
  • $\begingroup$ I saw those bounds on the Wiki page. I wanted a bound in terms of n. For counting sort, suppose half of the bits for the input are used for one key and the remaining bits are used for other keys. Suppose 0 is one such key. The largest number has a value of approximately 2^(n/2). So the range is approximately 2^(n/2). Which means the runtime is approximately n*2^(n/2). Is my analysis correct? $\endgroup$
    – Jesus is Lord
    Commented Nov 28, 2017 at 15:01
  • 1
    $\begingroup$ @WordsLikeJared : ​ ​ ​ I had mistakenly gotten the impression that you were using n for the number of elements, rather than the length of the input, which is why my previous comment was only for when n is the number of elements. ​ When n is the length of the input, the worst-case runtimes would presumably depend on the total order. ​ For the usual ordering on integers, I don't know. ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$
    – user12859
    Commented Nov 29, 2017 at 18:37
  • 1
    $\begingroup$ @WordsLikeJared - "And for radix sort: 'However, in general w cannot be considered a constant: if all n keys are distinct, ...'" ---- So expected density of keys is a clue as to whether a Radix sort might perform better than a comparison sort, and under O(n ln n). That is a useful knowledge. $\endgroup$
    – Craig Hicks
    Commented Nov 29, 2017 at 20:18
1
$\begingroup$

It is lower bound for all comparison based algorithms. Non-comparative algorithms such as Counting sort may work in linear time.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks! I was aware of counting-sort, but I wasn't considering that a real sort - I updated my question $\endgroup$
    – Jesus is Lord
    Commented Nov 26, 2017 at 22:57
  • 1
    $\begingroup$ @WordsLikeJared - Why would non-compare sorts not be considered real sorts? They are widely in industry. $\endgroup$
    – Craig Hicks
    Commented Nov 27, 2017 at 4:16
  • $\begingroup$ @CraigHicks I would consider non-compare sorts - that's what I was asking about. I didn't consider counting sort a "real" sort because: as the input grows large you're not adding new distinct elements; you're adding duplicates. I am curious, though - which non-compare sort are you thinking of? $\endgroup$
    – Jesus is Lord
    Commented Nov 27, 2017 at 4:21
  • $\begingroup$ @WordsLikeJared - With 'Counting Sort' the original input is kept. It is read in input order once at the beginning, and then once again at the end read in input order as the elements are copied to a separate ordered array. If there are input elements with duplicate keys, each duplicate will be read. They just don't have separate counts in the count array. So by your definition of 'real', isn't it real? In any case from the black box perspective, IO are indentical. See my answer above explaining the complexity for Counting Sort and LSD Radix. There is also a link to W'pedia with a table. $\endgroup$
    – Craig Hicks
    Commented Nov 27, 2017 at 6:53
  • 2
    $\begingroup$ Notable facts about "Counting Sort": (1) Initialization consists only of zeroing an array of length r. If that fits in the CPU cache, its very fast. (2) Running logic consists of two loops, each loop has no other branching conditions (e.g. if statements) than the loop end conditions. Branching conditions tend to slow down code execution because they prevent pipeline optimization. As for the loop end conditions, CPUs and compilers try to optimize loops by flattening the loops into blocks, so they're not as bad as if statements. If the problem fits, counting sort is worth considering. $\endgroup$
    – Craig Hicks
    Commented Nov 28, 2017 at 2:26
1
$\begingroup$

Another example for a linear time sorting algorithm is Bucket Sort when used with (strongly) limited keys.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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