sorting algorithm
Hi
The Fastest Sorting Algorithm?
Do you belive it?
Sorting n integers in O(n log(log n))
Which sorting algorithm is the fastest? Ask this question to any group of programmers and you'll get an animated discussion. Of course, there is no one answer. It depends not only on the algorithm, but also on the computer, data, and implementation. However, if you count the number of operations needed to sort integer numbers on a standard von Neumann computer, there is a clear winner -- the algorithm presented in the paper "Sorting In Linear Time?" by A. Andersson, T. Hagerup, S. Nilsson, and R. Raman (Proceedings of the 27th Annual ACM Symposium on the Theory of Computing, 1995). It sorts n integers in time proportional to n log log n. In this article, I'll give you a complete description of this algorithm.
Can it be done even faster? No one knows. We only know that it can't possibly be done using less than n operations: An algorithm using fewer operations than that can't look at each of the n numbers and, therefore, might leave some of the numbers out of order.
Even though the n log log n time-sorting algorithm came about as a theoretical game, its real-life performance is good. A C implementation like nloglogn.c ( available electronically; see "Resource Center," page 5) with no particular optimizations runs faster on a typical 32-bit machine than many standard textbook sorting algorithms.
1. h**p://www.ddj.com/documents/s=886/ddj0004d/0004d.htm
* -> t
tnx