title: How to speed up external merge sort in Java
body: <p>I am writing code for the external merge sort. The idea is that the input files contain too many numbers to be stored in an array so you read some of it and put it into files to be stored. Here's my code. While it runs fast, it is not fast enough. I was wondering if you can think of any improvements I can make on the code. Note that at first, I sort every 1m integers together so I skip iterations of the merging algorithm.</p>
  
  <pre><code>import java.io.BufferedInputStream;
  import java.io.BufferedOutputStream;
  import java.io.DataInputStream;
  import java.io.DataOutputStream;
  import java.io.FileInputStream;
  import java.io.FileNotFoundException;
  import java.io.IOException;
  import java.io.RandomAccessFile;
  import java.security.DigestInputStream;
  import java.security.MessageDigest;
  import java.security.NoSuchAlgorithmException;
  import java.util.Arrays;
  
  public class ExternalSort {
  
      public static void sort(String f1, String f2) throws Exception {
          RandomAccessFile raf1 = new RandomAccessFile(f1, "rw");
          RandomAccessFile raf2 = new RandomAccessFile(f2, "rw");
          int fileByteSize = (int) (raf1.length() / 4);
          int size = Math.min(1000000, fileByteSize);
          externalSort(f1, f2, size);  
          boolean writeToOriginal = true;
          DataOutputStream dos;
          while (size &lt;= fileByteSize) {
              if (writeToOriginal) {
                  raf1.seek(0);
                  dos = new DataOutputStream(new BufferedOutputStream(
                          new MyFileOutputStream(raf1.getFD())));
              } else {
                  raf2.seek(0);
                  dos = new DataOutputStream(new BufferedOutputStream(
                          new MyFileOutputStream(raf2.getFD())));
              }
              for (int i = 0; i &lt; fileByteSize; i += 2 * size) {
                  if (writeToOriginal) {
                      dos = merge(f2, dos, i, size);
                  } else {
                      dos = merge(f1, dos, i, size);
                  }
              }
              dos.flush();
              writeToOriginal = !writeToOriginal;
              size *= 2;
          }
          if (writeToOriginal)
          {
              raf1.seek(0);
              raf2.seek(0);
              dos = new DataOutputStream(new BufferedOutputStream(
                      new MyFileOutputStream(raf1.getFD())));
              int i = 0;
              while (i &lt; raf2.length() / 4){
                  dos.writeInt(raf2.readInt());
                  i++;
              }   
              dos.flush();
          }
      }
  
      public static void externalSort(String f1, String f2, int size) throws Exception{
  
          RandomAccessFile raf1 = new RandomAccessFile(f1, "rw");
          RandomAccessFile raf2 = new RandomAccessFile(f2, "rw");
  
          int fileByteSize = (int) (raf1.length() / 4);
  
          int[] array = new int[size];
          DataInputStream dis = new DataInputStream(new BufferedInputStream(
                  new MyFileInputStream(raf1.getFD())));
          DataOutputStream dos = new DataOutputStream(new BufferedOutputStream(
                  new MyFileOutputStream(raf2.getFD())));
  
          int count = 0;
          while (count &lt; fileByteSize){
              for (int k = 0; k &lt; size; ++k){
                  array[k] = dis.readInt();
              }
              count += size;
              Arrays.sort(array);
              for (int k = 0; k &lt; size; ++k){
                  dos.writeInt(array[k]);
              }       
          }
          dos.flush();
          raf1.close();
          raf2.close();
          dis.close();
          dos.close();
      }
  
      public static DataOutputStream merge(String file,
              DataOutputStream dos, int start, int size) throws IOException {
          RandomAccessFile raf = new RandomAccessFile(file, "rw");
          RandomAccessFile raf2 = new RandomAccessFile(file, "rw");
  
          int fileByteSize = (int) (raf.length() / 4);
          raf.seek(4 * start);
          raf2.seek(4 *start);
          DataInputStream dis = new DataInputStream(new BufferedInputStream(
                  new MyFileInputStream(raf.getFD())));
          DataInputStream dis3 = new DataInputStream(new BufferedInputStream(
                  new MyFileInputStream(raf2.getFD())));
          int i = 0;
          int j = 0;
          int max = size * 2;
  
          int a = dis.readInt();
  
          int b;
          if (start + size &lt; fileByteSize) {
              dis3.skip(4 * size);
              b = dis3.readInt();
          } else {
              b = Integer.MAX_VALUE;
              j = size;
          }
          while (i + j &lt; max) {
              if (j == size || (a &lt;= b &amp;&amp; i != size)) {
                  dos.writeInt(a);
                  i++;
                  if (start + i == fileByteSize) {
                      i = size;
                  } else if (i != size) {
                      a = dis.readInt();
                  }
              } else {
                  dos.writeInt(b);
                  j++;
                  if (start + size + j == fileByteSize) {
                      j = size;
                  } else if (j != size) { 
  
                      b = dis3.readInt();
                  }
              }
          }
          raf.close();
          raf2.close();
          return dos;
      }
  
      public static void main(String[] args) throws Exception {
          String f1 = args[0];
          String f2 = args[1];
  
          sort(f1, f2);
  
       }
  }
  </code></pre>