Problem Detail: I have about $500000000$, $64$-bit integers, so these numbers are very large. I want to sort them as quickly as possible. I have couple of questions:
- What data structure do you suggest for storing this data?
- What algorithm do you suggest for sorting these numbers?
I’m concerned about speed.
Asked By : Lrrr
Answered By : jmite
You’re not going to get much in the way of programming tips here, this is a site for computer science, not programming. For the sorting algorithm, you probably want to use Radix Sort, which will run in time $O(k n)$, for you $k = 64$ and $n = 500 000 000$. For the storing of these numbers, you might want to look into compressed data structures. However, these are necessarily going to bring some overhead. You’re looking at approximately 4GB of memory, which is reasonable on many modern machines. As you will learn in computer science, there is often a tradeoff between time and space. Here, you must choose between a fast data structure and a space-efficient data structure. EDIT: I change the time complexity to $O(kn)$, I’d mistyped and originally written $O(klog n)$. Sadly, it’s impossible to sort a list without actually looking at the entire contents of the list.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/13290
