5
$\begingroup$

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:

  1. What data structure do you suggest for storing this data?

  2. What algorithm do you suggest for sorting these numbers?

I'm concerned about speed.

$\endgroup$
2
5
$\begingroup$

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(k\log n)$. Sadly, it's impossible to sort a list without actually looking at the entire contents of the list.

$\endgroup$
1
$\begingroup$

Parallel processing is your solution, and GPU would do that. Since you have a large chunk of data (4GB) to be sorted, GPU would definitely outperform CPU's execution time.

See http://www.nvidia.com/docs/IO/67073/nvr-2008-001.pdf for details of an efficient parallel GPU sort.

$\endgroup$
2
  • 3
    $\begingroup$ This is not necessarily true. GPUs are good at performing a single branch-free mathematical operation on multiple sets of data. Sorting is a very branch-heavy operation, so a GPU would likely present much more overhead. Additionally, not all GPUs can actually store 4GB of data these days, so there would be tons of overhead from transferring data back and forth. Paralellism might help, but it also might introduce too much overhead. At the very least, I'd want to see a paper showing a GPU sorting algorithm with performance results. $\endgroup$ – jmite Jul 17 '13 at 6:01
  • $\begingroup$ lol. Instead of guessing, better off to verify from documentation of GPUs. Following site would help you: nvidia.com/docs/IO/67073/nvr-2008-001.pdf GPU would take chuncks of data (not byte by byte) from RAM, perform the sorting, and write back to RAM in O(logn) steps. $\endgroup$ – kaka Jul 17 '13 at 7:01
1
$\begingroup$

With some work on your part, you might be able to use an O(n) method. That's where you have a big hash table, and the hash function is one that preserves order, such as just grabbing the first k bits.

If the distribution of numbers is highly non-uniform, it could be important to first get a rough empirical distribution, by sampling a subset of numbers from the set and sorting them. Then you use an interpolated inverse of the distribution function to assign each number to a cell.

Then you sort the contents of each cell, which should not take too long if there are enough cells that each one does not contain too many numbers.

Finally you just read it all out sequentially.

Complicated? Yes. Fast? Yes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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