How would you sort 1 million 32-bit integers in 2MB of RAM?

Question

Please, provide code examples in a language of your choice.

Update: No constraints set on external storage.

Example: Integers are received/sent via network. There is a sufficient space on local disk for intermediate results.

Solution 1

Sorting a million 32-bit integers in 2MB of RAM using Python by Guido van Rossum

Solution 2

Split the problem into pieces small enough to fit into available memory, then use merge sort to combine them.

Solution 3

1 million 32-bit integers = 4 MB of memory.

You should sort them using some algorithm that uses external storage. Mergesort, for example.

Solution 4

You need to provide more information. What extra storage is available? Where are you supposed to store the result?

Otherwise, the most general answer: 1. load the fist half of data into memory (2MB), sort it by any method, output it to file. 2. load the second half of data into memory (2MB), sort it by any method, keep it in memory. 3. use merge algorithm to merge the two sorted halves and output the complete sorted data set to a file.

Solution 5

This wikipedia article on External Sorting have some useful information.

View more solutions

Comments

[Omar Kooheji]

probably best solution, exept you also want to have enough working space in memory to sort them...

[med]

Wouldn't help much. Or wouldn't help at all if all numbers are bigger than 65535.

[jfs]

I'm interested in code examples (I've already read theoretical aspects in Knuth)

[Adam Hawes]

You'd waste more space keeping track of types than you'd save!

[Noah Tony]

Guido should first optimize its website. Why he didn't take white background and white font color ;-) Looks more better