External MergeSort Sample Code

Today I practiced external merge sort just for fun. Here is the java code, for merge-sorting 5 sorted files, each of which contains a list of sorted integers. The input are out0.txt, out1.txt, out2.txt, out3.txt, out4.txt, output is sorted.txt.

import java.io.FileWriter;

import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;

public class ExternalMergeSort
{
public static void main(String[] args) throws Exception
{
// initialize n buffers for merge sort
List bufferList = new ArrayList();
for (int i = 0; i < 5; i++)
{
bufferList.add(new MergeSortBuffer("out" + i + ".txt"));
}

// output stream
PrintWriter out = new PrintWriter(new FileWriter("sorted.txt"));

// store merge sort result into output buffer
int[] outputBuf = new int[1000];

// merge until only one mergebuffer left
while (bufferList.size() > 1)
{
int min = -1;
int minPtr = -1;
for (int i = 0; i < bufferList.size(); i++)
{
if (minPtr < 0 || bufferList.get(i).pokeNext() < min)
{
min = bufferList.get(i).pokeNext(); minPtr = i;
}
}

// now we got minPtr buffer, write it out
out.println(bufferList.get(minPtr).getNext());

// remove the maxPtr buffer if it doesn't have elements anymore
if (!bufferList.get(minPtr).hasNext())
{
bufferList.remove(minPtr);
}
}

// output last buffer
MergeSortBuffer buf = bufferList.get(0);
while(buf.hasNext())
{
out.println(buf.getNext());
}

out.close();
}
}

--------------------------------------------------

import java.io.BufferedReader;
import java.io.FileReader;

public class MergeSortBuffer
{
private BufferedReader reader;
private int[] buf = new int[1000];
private int bufSize;
private int start;

public MergeSortBuffer(String fileName) throws Exception
{
reader = new BufferedReader(new FileReader(fileName));
refillBuf();
}

public boolean hasNext() throws Exception
{
return bufSize > 0;
}

public int pokeNext() throws Exception
{
return buf[start];
}

public int getNext() throws Exception
{
int next = buf[start];
start++;
if (start >= bufSize)
{
refillBuf();
}
return next;
}

private void refillBuf() throws Exception
{
int i = -1;
while (true)
{
String line = reader.readLine();
if (line == null || line.equals(""))
{
break;
}
i++; buf[i] = Integer.parseInt(line);
if (i + 1 == buf.length)
{
break;
}
}

start = 0;
bufSize = i + 1;
}
}