External / File-based mergesort
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;
    }

}