• Post Reply Bookmark Topic Watch Topic
  • New Topic

Sorting data in an external file  RSS feed

 
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
--------------------------------------------------------------------------------
An external file contains N unique keys(integers). I have to put them in ascending order. Each block contains M keys, and thus the file contains n=N/M blocks B1,B2...Bn.
I can assume that the number of blocks, n, is an exact power of 2.
The program can access only enough internal memory to manipulate about 3*M numbers(three blocks worth)at a time. for internal sorting I can use any method of sorting.
 
author and iconoclast
Sheriff
Posts: 24217
38
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Tony,

Welcome to JavaRanch!

Please don't post the same question to more than one forum -- it just wastes people's time if they answer a question that's already been answered well elsewhere.

Regarding your problem: Google for "external sort". Lots of good references. The basic idea is to sort each piece (your "3 block chunks") independently, and then merge them together, pairwise or N-wise. In Java, you'd likely use the static sort() methods in the Arrays class to do the local sorts.
 
Consider Paul's rocket mass heater.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!