Sorting 1 million queries

Question

I have 1 million queries on disk to sort, my local memory/cache can store
up to 1 thousand queries, how can I perform sort?

This is a google interview question. Can someone help me find the answer?

Sort by what? What have you considered so far? Research different sorts, esp. merge sort. — Martin James, Aug 20 '12 at 11:34
related: [How would you sort 1 million 32-bit integers in 2MB of RAM?](http://stackoverflow.com/q/134158/4279) — jfs, Aug 20 '12 at 12:13

score 4 · Accepted Answer · answered Aug 20 '12 at 11:33

4

You load 1000 queries in memory and sort them using quicksort, writing them to a file. In the end you'll have 1000 such files.

You then go on to merging the files using, you guessed it, mergesort.

That's how I'd do it. By no means the most optimal solution.

answered Aug 20 '12 at 11:33

Luchian Grigore

253,575
64
457
625

score 1 · Answer 2 · answered Aug 20 '12 at 11:34

1

External merge sort can be employed to achieve that.

answered Aug 20 '12 at 11:34

twoflower

6,788
2
33
44

score 1 · Answer 3 · answered Aug 20 '12 at 11:35

1

Get more memory. A query is not that big. It's a question that tests whether you can think outside the box.

answered Aug 20 '12 at 11:35

MSalters

173,980
10
155
350

score 1 · Answer 4 · answered Aug 20 '12 at 11:41

1

I am lazy: Read all queries (1,000 each), dump them in a database, then SELECT ORDER BY anything. If it is Google asking, they'll have databases anyway...

answered Aug 20 '12 at 11:41

f_puras

2,521
4
33
38

Sorting 1 million queries

4 Answers4