Sorting algorithms

[Antrax]

A lecturer mentioned there exist sorting algorithms, not based on comparisons of course, that sort in better complexity than nlogn, without making any assumptions on the input (other than possibly the fact it's n numbers and not just entities with some order relation defined on them).
Is anyone familiar with these? Can point me in the direction of one, or even better, explain how such a thing would work?
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[Samadhi]

[Antrax]

Some sort of bit computations. I'm not entirely sure myself, which is why I'm asking, because I was surprised to find out such algorithms exist.
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[Talzor]

He is probably thinking about Radix sort.

[Antrax]

No, Radix Sort (and Bucket/Counting sort) assumes the input is bounded. Otherwise the complexity is not better than nlogn.
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[Lepton*]

I don't understand the field, but it seems like the Radix Sort could be implemented in such a way as to deal with data with an unknown range. I do something similar in an complicated n-dimensional numerical integrator on which I am working.

[Bicho the Inhaler]

Radix sorting doesn't require the input to be bounded. This is clearly true, e. g., for LSB algorithms. (Sort on the least significant bit or character using a stable sorting algorithm. Then sort on the second-least significant bit or character using a stable algorithm. Keep going until you run out of bits or characters.)

[Antrax]

The complexity of Radix Sort is O(k*n) where k is the "size" of the input elements. So, when sorting n numbers, each 2^(2^(2^n)), you get a run time that is far worse than nlogn, so this algorithm's complexity depends on the input being bounded to something reasonable. So, this is not what I was asking about.
extro?
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[Bicho the Inhaler]

Antrax, while that's true, that point is unfair unless you scrutinize other sorting algorithms in the same light. When analyzing a comparison-based sorting algorithm, we usually abstract away the time taken to compare elements. A comparison-based algorithm that is O(n*log(n)) is therefore actually O(n*log(n)*k), where k is the length of the input numbers (since comparison is an O(k) operation). Your point therefore isn't a sensible objection.

[Antrax]

Bicho, I disagree, though mostly because that's what I was taught. Also because I know for a fact he didn't mean Radix sort and friends, but rather something even stronger (I asked the professor).
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[Nsof]

There are some sorting algs here http://en.wikipedia.org/wiki/Sort_algorithm some of which if run on a specialized hardware will run at O(n) time.
_________________
Will sell this place for beer

[extro...*]

[extro...*]

I don't think there can be a sorting algorithm that does better than O(n lg n) average or worst case without some significant restrictions on the input it can handle.

For comparison based sorts, the proof of that is based on the fact that a binary tree with n! leaf nodes has O(n lg n) depth. Any sorting algorithm must decide which of the n! possible permutations of the n element list it is sorting is the correct one (the sorted one). Whether they're comparisons or some other operations, I think you can always build a tree representing all possible sequences of operations that will be performed by that algorithm for all possible input sequences of size n, that tree then having at least n! leaf nodes, and thus a depth bounded by O(n lg n). That's an informal argument - not a proof - but I think the principle for a proof is there.

[Antrax]

Yeah, that's the proof we've seen in class a while back.
In any case, now my interest is really piqued, so I'll find that professor tomorrow and ask him for a name. He specifically said better than nlogn for worst case without having to assume anything on the input apart from it being numbers.
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[Bicho the Inhaler]

[Nsof]

did you look at http://en.wikipedia.org/wiki/Bead_sort and http://en.wikipedia.org/wiki/Pancake_sorting?
_________________
Will sell this place for beer

[Bicho the Inhaler]

I also thought about MSB radix algorithms. This will assume all the numbers are the same length. First sort everything by the most significant bit. The array now has two sections: numbers beginning with 0 and numbers beginning with 1. Recurse on each section, ignoring the first bit. The basis case is a subarray with one element.

Its complexity is Theta(n*j), where j is the average number of bit comparisons needed to distinguish adjacent elements of the sorted list. (The sorting at each level of recursion can be implemented in such a way that each bit at that level is visited exactly once. Overall, any given bit of a given input number is visited at most once, and it is visited only if necessary to distinguish that number from one of the numbers next to it.) However, if the numbers are long, then I don't think this can be better than Omega(n*log(n)). If the numbers are extremely long and some of them are equal or nearly equal, then it could be a lot worse than n*log(n), but then I think the same would apply to all sorting algorithms, since it takes a lot of work just to tell the numbers apart.

[Jack_Ian]

Assuming we're talking about integers, comparing individual bits of numbers takes longer than comparing the actual numbers since the bit must first be extracted before it's compared and the comparison is performed on two full words.

In real situations, the problem involves looking at the broader picture.
Sometimes, the fastest solutions involve minimising the "swaps" or minimising memory paging or caching chunks of the data to sort in memory and then merging the chunks.

I remember one case where I was forced to slow down my sorting as it was so efficient that it hogged computer resources and caused a noticeable drop in performance for other users on the system. I was particularly proud of my solution at the time, as it was written in COBOL and just screamed along (no mean feat for a COBOL program). It almost killed me to introduce the delay in my code. I remember it was encased by a large comment describing the reasons why it was done and who had forced me to do it and how the whole thing just sucked.

[Bicho the Inhaler]

[extro...*]

[Antrax]

[Antrax]

And, typically, he just replied. Here's his email:

[Jack_Ian]

[Antrax]

So what'd you win?
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[Jack_Ian]