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.

Answer 1

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

Answer 2

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

Answer 3

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

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

Answer 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.

Answer 5

This wikipedia article on External Sorting have some useful information.

Answer 6

Dual tournament sort with polyphased merge

#!/usr/bin/env python
import random
from sort import Pickle, Polyphase


nrecords = 1000000
available_memory = 2000000 # number of bytes
    #NOTE: it doesn't count memory required by Python interpreter 

record_size = 24 # (20 + 4) number of bytes per element in a Python list
heap_size = available_memory / record_size 
p = Polyphase(compare=lambda x,y: cmp(y, x), # descending order
              file_maker=Pickle, 
              verbose=True,
              heap_size=heap_size,
              max_files=4 * (nrecords / heap_size + 1))

# put records
maxel = 1000000000
for _ in xrange(nrecords):
    p.put(random.randrange(maxel))

# get sorted records
last = maxel
for n, el in enumerate(p.get_all()):
    if el > last: # elements must be in descending order
        print "not sorted %d: %d %d" % (n, el ,last)
        break
    last = el

assert nrecords == (n + 1) # check all records read

Answer 7

Here's a valid and fun solution.

Load half the numbers into memory. Heap sort them in place and write the output to a file. Repeat for the other half. Use external sort (basically a merge sort that takes file i/o into account) to merge the two files.

Aside: Make heap sort faster in the face of slow external storage:

• Start constructing the heap before all the integers are in memory.

• Start putting the integers back into the output file while heap sort is still extracting elements

Answer 8

• Um, store them all in a file.
• Memory map the file (you said there was only 2M of RAM; let's assume the address space is large enough to memory map a file).
• Sort them using the file backing store as if it were real memory now!

Answer 9

As people above mention type int of 32bit 4 MB.

To fit as much "Number" as possible into as little of space as possible using the types int, short and char in C++. You could be slick(but have odd dirty code) by doing several types of casting to stuff things everywhere.

Here it is off the edge of my seat.

anything that is less than 2^8(0 - 255) gets stored as a char (1 byte data type)

anything that is less than 2^16(256 - 65535) and > 2^8 gets stored as a short ( 2 byte data type)

The rest of the values would be put into int. ( 4 byte data type)

You would want to specify where the char section starts and ends, where the short section starts and ends, and where the int section starts and ends.

Answer 10

No example, but Bucket Sort has relatively low complexity and is easy enough to implement