Comment by nokcha | Hacker News Reader

Comment by nokcha | Hacker News Reader

Parent Full thread

>It is possible, with some proper insight and approaches, to sort general datastructures in linear time on modern computing hardware. The speed limit of sort is O(n) with some extra constant cost (often accrued by allocation).

There is a well-known proof from information theory that the problem of sorting n distinct items has a worst-case time complexity of Ω(n log n) fixed-bitwidth operations: (1) Since each of the n items is distinct, the average number of bits needed to encode each item is Ω(log n). (2) In the worst case, in order to correctly sort the items, each bit of each item needs to be read. (3) Therefore, sorting the list requires reading Ω(n log n) bits.

So, I'm not sure how to understand the claim that their algorithm operates in "linear time". Are they saying O(n) operations where each operation operates on O(log n) bits?

[Edit: See below response from kraghen: The time is linear in the total size of the data, not in the number of items. I'll leave this comment up in case anyone has the same misunderstanding that I had.]

Discrimination runs in linear time not in the number of items but in the total size of the data. If you have n items each of size k it takes O(kn). Conventional sorting often assumes that you can compare keys of size k in constant time and therefore gets O(n lg n) but a more honest analysis would yield O(kn log n) for (say) merge sort.

Thank you, that cleared up my misunderstanding.

The bound on string sorting is typically written as O(n log n + D), where D is the sum of distinguishing prefixes, ie input length minus some fluff. Since D >= n log n we already have linearity on input length.

Are you saying that you can sort strings in O(n log n + D) using a conventional sorting algorithm such as merge sort? If so, I don't understand why D would be an additive factor implying that each string is only involved in a constant number of comparisons.

(I wasn't, by the way, only considering strings when discussing variable sized keys -- the beauty of discrimination is that we essentially reduce all sorting problems to string sorting.)

A conventional sorting algorithm such as Multikey Quicksort.

http://people.mpi-inf.mpg.de/~sanders/courses/algdat03/salgd...

Sorry, I was being imprecise. By conventional I meant comparison-based sorting functions that are polymorphic in the element type and thus not allowed to examine individual bytes.

Multikey Quicksort indeed looks like a special case of discrimination, exploiting some of the same principles.

When people say "conventional" sorting algorithms, they're usually talking about sorting algorithms based around pairwise comparison functions.

I note on slide 14 of this presentation, it looks like this is sort of the discriminator for selecting a better partitioning scheme. So it looks to me like this actually leverages a similar principle?

As we've seen in this thread and others, there are some other ways to measure and/or process that have different characteristics. Surely all of these deserve attention! So, thanks very much for sharing this.

> There is a well-known proof from information theory [...]

Remember that this proof is talking in terms of the number of comparisons necessary to sort n items. The moment you stop comparing data, like in radix sort (or more generally, bucket sort), that all flies out the window.

> Are they saying O(n) operations where each operation operates on O(log n) bits

Yes, as in any other claimed complexity about an algorithm. According to your proof finding the maximum in a list is Ω(n log n), which isn't the commonly used measure.

Reply on news.ycombinator.com