Massive amounts of data

The expected answer is External sort.

Bubble sort is only good for data sets that are already almost sorted.

Otherwise, it is time-consuming because it requires O( $n^2$ ) time, where $n$ is the size of input data.

A size limit of $2.25 \ GB$ , tells you that, don’t bring all the data into memory. You only bring part of the data into memory.

$Algorithm:$

Assume that you have $N\ MB$ of memory available, where $N \leq 100$ .

1. Divide the $2.25 \ GB$ file into $K$ chunks, where $N \times K = 2.25 \ GB$ .

2. Bring each chunk into memory and sort the $N \ MB$ lines, as usual, using any known $O(N \ log \ N)$ algorithm. Save the lines back to the file.

3. Bring the next chunk into memory and sort.

4. Once you’re done, merge them one by one.

The above algorithm is known as $external \ sort$ algorithm.