External / File-based mergesort I've implemented an external mergesort to sort a file consisting of Java int primitives, however it is horribly slow (fortunately it does at least work).

Very little happens in the sort method: it just recursively calls merge with blockSize doubling each call and swapping input and output files each time.

How could I be losing so much time here?

//Merge stage of external mergesort
//Read from input file, already sorted into blocks of size blockSize
//Write to output file, sorted into blocks of 2*blockSize
public static void merge(String inputFile, String outputFile, long blockSize)
    throws IOException
{
  //readers for block1/2
  FileInputStream fis1 = new FileInputStream(inputFile);
  DataInputStream dis1 = new DataInputStream(fis1);
  FileInputStream fis2 = new FileInputStream(inputFile);
  DataInputStream dis2 = new DataInputStream(fis2);

  //writer to output file
  FileOutputStream fos = new FileOutputStream(outputFile);
  DataOutputStream dos = new DataOutputStream(fos);

  // merging 2 sub lists
  // go along pairs of blocks in inputFile
  // continue until end of input

  //initialise block2 at right position
  dis2.skipBytes((int) blockSize);

  //while we haven't reached the end of the file
  while (dis1.available() &gt; 0)
    {
      // if block1 is last block, copy block1 to output
      if (dis2.available() &lt;= 0)
        {
          while (dis1.available() &gt; 0) 
            dos.writeInt(dis1.readInt());
          break;
        }
      // if block1 not last block, merge block1 and block2
      else
        {
          long block1Pos = 0;
          long block2Pos = 0;
          boolean block1Over = false;
          boolean block2Over = false;

          //data read from each block
          int e1 = dis1.readInt();
          int e2 = dis2.readInt();

          //keep going until fully examined both blocks
          while (!block1Over | !block2Over)
            {
              //copy from block 1 if:
              //  block1 hasnt been fully examined AND
              //  block1 element less than block2s OR block2 has been fully examined
              while ( !block1Over &amp; ((e1 &lt;= e2) | block2Over) )
                {
                  dos.writeInt(e1); block1Pos += 4;
                  if (block1Pos &lt; blockSize &amp; dis1.available() &gt; 0) 
                    e1 = dis1.readInt();
                  else 
                    block1Over = true;
                }
              //same for block2
              while ( !block2Over &amp; ((e2 &lt; e1) | block1Over) )
                {
                  dos.writeInt(e2); block2Pos += 4;
                  if (block2Pos &lt; blockSize &amp; dis2.available() &gt; 0) 
                    e2 = dis2.readInt();
                  else 
                    block2Over = true;
                }
            }
        }
      // skip to next blocks
      dis1.skipBytes((int) blockSize);
      dis2.skipBytes((int) blockSize);
    }
  dis1.close();
  dis2.close();
  dos.close();
  fos.close();
}
Steve is absolutely right that adding a buffered layer between the Data input/output streams and the File input/output streams, will make things work a whole lot better. I would also suggest changing to use a try-with-resources system, which will also close, and otherwise manage the files in a better way:

try (DataInputStream dis1 = new DataInputStream(new BufferedInputStream(new FileInputStream(inputFile)));
     DataInputStream dis2 = new DataInputStream(new BufferedInputStream(new FileInputStream(inputFile)));
     DataOutputStream dos = new DataOutputStream(new BufferedOutputStream(new FileOutputStream(outputFile))); ) {

    //initialise block2 at right position
    dis2.skipBytes((int) blockSize);

    ... do other work ...

}


Now, your input/output is buffered, and it's closed cleanly, and there are no leaks. The input/output is also buffered, leading to fewer IO's, and more efficient processing.

This will likely make a huge difference in performance, but, I suspect that using NIO (ByteBuffer) operations (especially with memory-mapped IO) will be faster again. Consider using FileChannel operations that reduce the amount of memory copies that are made of the data in the file.

UPDATE:

I have taken some time to run some tests and use some strategies that I am familiar with from high-performance systems. As I suspected, a FilChannel with Memory-mapped IO is far faster.

On my computer, a file with 400,000 int values takes about 15 seconds to sort using your system. When I used Buffered IO, it took 1.5 seconds (10 times faster).

I then rewrote the system using a couple of tricks:


use small sorts for blocks of 32 integers.
then use merging for larger, and larger blocks.
use memory mapped IO to do the file accesses


The result was a sort in 0.096 seconds, or 150 times faster than your code.

Now, this code is not exactly simple, so, be warned that it is a little obscure.

The first thing I did though, was create a class to abstract away the low-level IO:

private static final class FastFile implements AutoCloseable {
    private final Path path;
    private final FileChannel channel;
    private final long size;
    private MappedByteBuffer buffer = null;
    private long mapPosition = -1;

    public FastFile(final Path folder, final long size) throws IOException {
        this.size = size;
        this.path = Files.createTempFile(folder, "tmpdata", ".dat");
        this.channel = FileChannel.open(path, StandardOpenOption.TRUNCATE_EXISTING, StandardOpenOption.WRITE, StandardOpenOption.READ);
        // Create the file with the right size.
        channel.write(ByteBuffer.allocate(1), size - 1);
        resetFile();
    }

    @Override
    public void close() throws Exception {
        channel.force(true);
        channel.close();
        buffer = null;
    }

    private final void relocate(final long filepos) throws IOException {
        if (filepos &gt;= size) {
            throw new IllegalArgumentException("Illegal file position " + filepos + " in file of size " + size); 
        }
        final long mappos = filepos &gt;&gt;&gt; MAPPEDSHIFT;
        if (mappos != mapPosition) {
            final long pos = mappos &lt;&lt; MAPPEDSHIFT;
            final long len = Math.min(size - pos, MAPPEDSIZE);
            buffer = channel.map(MapMode.READ_WRITE, pos, len);
            buffer.load();
            System.out.println("Move to position " + pos + " and length " + len);
            mapPosition = mappos;
        }
    }

    public void resetFile() throws IOException {
        relocate(0);
    }


    public int getInt(final long intPosition) throws IOException {
        final long filepos = intPosition &lt;&lt; 2;
        final int offset = (int)(filepos &amp; MAPPEDMASK);
        relocate(filepos);
        return buffer.getInt(offset);
    }

    public void putInt(final long intPosition, final int intValue) throws IOException {
        final long filepos = intPosition &lt;&lt; 2;
        final int offset = (int)(filepos &amp; MAPPEDMASK);
        relocate(filepos);
        buffer.putInt(offset, intValue);
    }

    public void rename(String targetName) throws IOException {
        Files.move(path, Paths.get(targetName));
    }

    public void delete() throws IOException {
        Files.delete(path);
    }

}


The above class can take a file, and read/write ints at any particular place. It first creates the file, and sets it to be the right size.

It is read/write and random-access. It can write an int at any position. The expensive part of the operation is relocating the buffer, but, that will happen seldom.

Using that file class, I have the following sort code:

private static void mergeSortSmart(String sourceName, String targetName) throws IOException {
    long start = System.currentTimeMillis();
    Path source = Paths.get(sourceName);
    final long size = Files.size(source);
    final long intvals = size &gt;&gt;&gt; 2; // number of actual integer values (4 bytes per int).

    Path target = Paths.get(targetName).toAbsolutePath();
    if (Files.exists(target)) {
        Files.delete(target);
    }
    Path tdir = target.getParent();
    FastFile filea = new FastFile(tdir, size);
    FastFile fileb = new FastFile(tdir, size);

    int blockSize = 32;

    // copy the source data to a fast file, but do 32-size block int sorts
    // before merge-sorting.
    copyAndMicroSort(source, size, filea, blockSize);

    // then do iterative merge sorts.
    for (long bs = blockSize; bs &lt; size; bs *= 2) {
        mergeFast(filea, fileb, intvals, bs);
        FastFile tmp = filea;
        filea = fileb;
        fileb = tmp;
    }
    // rename the sorted file.
    filea.rename(targetName);
    // delete the temp file.
    fileb.delete();
    System.out.printf("Sorted in %.3fs%n", (System.currentTimeMillis() - start)/ 1000.0);
}


The copyAndMicroSort is simple:

private static void copyAndMicroSort(Path source, long size, FastFile filea, final int batchSize) throws IOException {
    try (DataInputStream di = new DataInputStream(new BufferedInputStream(new FileInputStream(source.toFile())))) {
        long pos = 0;
        int cnt = 0;
        long vcount = 0;
        int[] data = new int[batchSize];
        while (pos &lt; size) {
            if (cnt == data.length) {
                appendSortedInts(data, cnt, filea, vcount);
                vcount += cnt;
                cnt = 0;
            }
            data[cnt++] = di.readInt();
            pos += 4; // size of int;
        }
        appendSortedInts(data, cnt, filea, vcount);
    }

}

private static void appendSortedInts(final int[] data, final int cnt, final FastFile filea,
        final long vcount) throws IOException {
    Arrays.sort(data, 0, cnt);
    for (int i = 0; i &lt; cnt; i++) {
        filea.putInt(vcount + i, data[i]);
    }
}


And the individual merge sorts are:

private static void mergeFast(final FastFile infile, final FastFile outfile, final long intCount, final long bs) throws IOException {
    long apos = 0;
    long bpos = bs;
    long outpos = 0;

    while (apos &lt; intCount) {
        long alimit = Math.min(bpos, intCount);
        long blimit = Math.min(alimit + bs, intCount);
        while (apos &lt; alimit &amp;&amp; bpos &lt; blimit) {
            int aval = infile.getInt(apos);
            int bval = infile.getInt(bpos);
            if (aval &lt;= bval) {
                outfile.putInt(outpos++, aval);
                apos++;
            } else {
                outfile.putInt(outpos++, bval);
                bpos++;
            }
        }
        while (apos &lt; alimit) {
            outfile.putInt(outpos++, infile.getInt(apos++));
        }
        while (bpos &lt; blimit) {
            outfile.putInt(outpos++, infile.getInt(bpos++));
        }
        apos += bs;
        bpos += bs;
    }

}