It sounds like they are asking for an external merge sort
Something like this, exceptI've done it for bytes not integers
public class ExternalMergeSort
{
int MemoryLimit = 100;
public void Sort(string filename, string newFilename)
{
List fileChunks = SplitFile(filename, MemoryLimit);
SortChunks(fileChunks);
Merge(fileChunks, newFilename, MemoryLimit);
}
public List SplitFile(string filename, int memoryLimit)
{
var filenames = new List();
string outFilename;
FileStream outStream = GetNewChunkStream(memoryLimit / 2, out outFilename);
filenames.Add(outFilename);
using (FileStream inStream = new FileStream(filename, FileMode.Open, FileAccess.Read, FileShare.Read, memoryLimit / 2))
{
int value = inStream.ReadByte();
while (value >= 0)
{
outStream.WriteByte((byte)value);
value = inStream.ReadByte();
if (value >= 0 && outStream.Length > memoryLimit)
{
outStream.Close();
outStream = GetNewChunkStream(memoryLimit / 2, out filename);
filenames.Add(filename);
}
}
outStream.Close();
return filenames;
}
}
private FileStream GetNewChunkStream(int bufferSize, out string filename)
{
filename = Path.GetTempFileName();
return new FileStream(filename, FileMode.Create, FileAccess.Write, FileShare.Write, bufferSize);
}
private void SortChunks(List filenames)
{
foreach (string filename in filenames)
{
byte[] bytes = File.ReadAllBytes(filename);
Array.Sort(bytes);
File.WriteAllBytes(filename, bytes);
}
}
private void Merge(List fileChunks, string outputFile, int memoryLimit)
{
var queue = new PriorityQueue();
// put 1 byte in for each stream
int bufferSize = memoryLimit / (fileChunks.Count + 1);
foreach (string filename in fileChunks)
{
var stream = new FileStream(filename, FileMode.Open, FileAccess.Read, FileShare.Read, bufferSize);
int value = stream.ReadByte();
if (value >= 0)
queue.Enqueue((byte)value, stream);
}
using (var outStream = new FileStream(outputFile, FileMode.Create, FileAccess.Write, FileShare.Write, bufferSize))
{
while (!queue.IsEmpty())
{
HeapNode current = queue.Dequeue();
outStream.WriteByte(current.Priority);
// read next byte
FileStream stream = current.Value;
int value = stream.ReadByte();
if (value >= 0)
queue.Enqueue((byte)value, stream);
}
}
}
}