sort a huge array

Question

what is the best way to sort a huge array. say I have 1G RAM, array is 16G. What is the most efficient method to do this? I got enough disk for files.

Which programming language are you intending to use? You seem to be most concerned about memory usage. What's the state of the virtual memory; do you even need to care? What's your definition of 'best' - time, minimized swapping, or other? — p.campbell
– p.campbell, Commented Feb 24, 2011 at 2:37
@p.campbell not a practical problem. Focus on algorithm and solution. Thanks :) — Josh Morrison
– Josh Morrison, Commented Feb 24, 2011 at 2:38
@p.campbell yeah kinda. I met another big file question before. so came up with this one. still preparing for Amazon interview. LOL~ — Josh Morrison
– Josh Morrison, Commented Feb 24, 2011 at 2:52

recursive · Accepted Answer · 2011-02-24 02:38:52Z

17

Split into chunks and sort 512MB at a time into 32 files. Then do a streaming merge sort of the files into one file.

answered Feb 24, 2011 at 2:38

recursive

86.5k36 gold badges155 silver badges246 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Travis Webb · Accepted Answer · 2011-02-24 03:06:33Z

4

If it's an array of integers, you can get by with a naive radix sort (O(n)) and use almost no RAM at all. First question would be "What kind of data is it?". If its arbitrary data, then an external mergesort is probably your best option.

-tjw

answered Feb 24, 2011 at 3:06

Travis Webb

15k9 gold badges59 silver badges111 bronze badges

Collectives™ on Stack Overflow

sort a huge array

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related