title: Different sorting algorithms fail on large arrays
body: <p>I am trying to sort the arrays using different algorithms. When I run the application with small number of arrays, it works and produces the results. When the arrays are larger than: 131072, it stops responding. </p>
  
  <p>What can be the reason? Is there anything wrong with this code?</p>
  
  <p>This is my function:</p>
  
  <pre><code>boolean runTest(String[] text, int[] number, String url, String out, Sort sort) {
    PrintWriter filename;
    boolean tobeReturned = true;
    String beforeSorting = "";
    String afterSorting = "";
  
    long startTime;
    double timeTaken;
    try {
      filename = createWriter(out);
  
      for(File directory : new File(url).listFiles()){
        File[] listOfFiles = directory.listFiles();     
        filename.println("Number of Records: \t" + directory.getName());
  
        for (File file : listOfFiles) {
          text = loadStrings(file);
          number = int(text);
          if (isSorted(number)) { beforeSorting = "Sorted";} else { beforeSorting = "NOT Sorted"; };
  
          startTime = startTime();       
          sort.sortInteger(number);        
          timeTaken = stopTime(startTime);
  
          if (isSorted(number)) { afterSorting = "Sorted"; } else { afterSorting = "NOT Sorted"; };
  
          filename.println("File Set " + file.getName() + ": \t\t" + beforeSorting + ": \t" + afterSorting + ": \t" + timeTaken);
          timeTaken = 0;
        }
        filename.println("\n");
      }
      filename.flush();
      filename.close();
    } 
    catch (Exception e) {
      tobeReturned = false;
    }
    return tobeReturned;
  }
  </code></pre>
  
  <p><strong>Interface:</strong></p>
  
  <pre><code>interface Sort{
     public int[] sortInteger(int[] input);
  }
  </code></pre>
  
  <p><strong>One of the sorting class (Insertion)</strong> </p>
  
  <pre><code>class Insertion implements Sort{
  
    Insertion() {
    }
  
    int[] sortInteger(int[] input) {
      int i, j, tobeSorted;
      for (i = 1; i &lt; input.length; i++) {
        tobeSorted = input[i];
        j = i;
        while (j &gt; 0 &amp;&amp; input[j - 1] &gt; tobeSorted) {
          input[j] = input[j - 1];
          j--;
        }
        input[j] = tobeSorted;
      }
      //println(input);
      return input;
    }
  }
  </code></pre>
  
  <p>Numbers folders:</p>
  
  <p><a href="https://i.stack.imgur.com/VAMNu.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/VAMNu.png" alt="enter image description here"></a></p>
  
  <p>Files:</p>
  
  <p><a href="https://i.stack.imgur.com/00ZE7.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/00ZE7.png" alt="enter image description here"></a></p>
  
  <p>Records:</p>
  
  <p><a href="https://i.stack.imgur.com/TarzJ.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/TarzJ.png" alt="enter image description here"></a></p>
  
  <p>Result of insertion sort:</p>
  
  <p><a href="https://i.stack.imgur.com/Qwlvj.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/Qwlvj.png" alt="enter image description here"></a></p>
  
  <p>Result of merge sort:</p>
  
  <p><a href="https://i.stack.imgur.com/N4toM.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/N4toM.png" alt="enter image description here"></a></p>
  
  <p>******UPDATE******</p>
  
  <p><strong>Full Simplified Processing Code</strong></p>
  
  <pre><code>import java.util.*; 
  
  long a = 9; // total loop, 9 means = 65536, 10 means = 131072 ...
  long b = 2;  // multiplier, 2 means = 512,1024,2048...
  long c = 512; // starting number
  long d = 5; // times random text file
  
  String url; 
  
  Insertion insertion;
  Merge merge;
  Bubble bubble;
  Shell shell;
  QuickSort quickSort;
  
  void setup() {
    url = sketchPath("_numbers/");  
  
    insertion = new Insertion();
    merge = new Merge();
    bubble = new Bubble();
    shell = new Shell();
    quickSort = new QuickSort();
  
    generateFiles(a,b,c,d);
  
    boolean runSortTest = false;
      runSortTest = runTest(url, "_results/a_insertion.txt", insertion);
      runSortTest = runTest(url, "_results/b_merge.txt", merge);
      runSortTest = runTest(url, "_results/c_bubble.txt", bubble);
      runSortTest = runTest(url, "_results/d_shell.txt", shell);
      runSortTest = runTest(url, "_results/e_quickSort.txt", quickSort);
  
      if(runSortTest){
        println("Done");
      }else{
        println("Error");
      }
  
  }
  
  boolean generateFiles(long totalLoop, long multiplier, long power, long fileNumber){
    PrintWriter pw;
    //int orderCount = 1;
    int count = 1;
    //boolean tobeReturned = true;
    try {
      for (int i = 1; i &lt; totalLoop; i = i+1) {   
        for (int j = 1; j &lt; fileNumber+1; j = j+1) {
          pw = createWriter("/_numbers/" + power + "/" + count + ".txt"); 
  
          for (int k = 0; k &lt; power; k = k+1) { 
            pw.println(randomNumber(0, power));
            //pw.write(int(randomNumber(0, power)) + "\t");
          }
          count++;
  
          pw.flush(); // Writes the remaining data to the file
          pw.close(); // Finishes the file
        }
        count = 1;
        //orderCount++;
        power *= multiplier; 
      }
      //orderCount = 1;
      return  true;
    } catch (Exception e) {
      return false;
    }
  }
  
  long randomNumber(long min, long max){
    long randomN = (long)random(min,(max + 1));
    return randomN;
  }
  
  //####################################################################################################
  //## Runs the test and produces a log file for each algorithms
  //####################################################################################################
  
  boolean runTest(String url, String out, Sort sort) {
    PrintWriter filename;
    boolean tobeReturned = true;
    String beforeSorting = "";
    String afterSorting = "";
  
    long startTime;
    double timeTaken;
    try {
      filename = createWriter(out);
  
      for(File directory : new File(url).listFiles()){
        File[] listOfFiles = directory.listFiles();     
        filename.println("Number of Records: \t" + directory.getName());
  
        for (File file : listOfFiles) {
          String[] text; int[] number;
          text = loadStrings(file);
          number = int(text);
          if (isSorted(number)) { beforeSorting = "Sorted";} else { beforeSorting = "NOT Sorted"; };
  
          startTime = startTime();       
          sort.sortInteger(number);        
          timeTaken = stopTime(startTime);
  
          if (isSorted(number)) { afterSorting = "Sorted"; } else { afterSorting = "NOT Sorted"; };
  
          filename.println("File Set " + file.getName() + ": \t\t" + beforeSorting + ": \t" + afterSorting + ": \t" + timeTaken);
          timeTaken = 0;
          Arrays.fill(text, null);
          number = null;
        }
        filename.println("\n");
      }
      filename.flush();
      filename.close();
  
    } 
    catch (Exception e) {
      e.printStackTrace();
      tobeReturned = false;
    }
    return tobeReturned;
  }
  
  
  
  boolean isSorted(int[] array) {
    for (int i = 0; i &lt; array.length-1; i ++) {
      if (array[i] &gt; array[i+1]) {
        return false;
      }
    }
    return true;
  }
  
  //####################################################################################################
  //## Time comparison
  //####################################################################################################
  
  long startTime() {
    return System.nanoTime();
  }
  
  double stopTime(long startTime) {
    double finalTime = (System.nanoTime() - startTime)/1000000000.0;
    return finalTime;
  }
  
  /*
  
  Interface
   # Last update: 20 October 2015 
  */
  
  interface Sort{
     public int[] sortInteger(int[] input);
  }
  
  /*
  
  Insertion class, implements Sort interface
   # Last update: 25 October 2015
  */
  
  
  class Insertion implements Sort{
  
    Insertion() {
    }
  
    int[] sortInteger(int[] input) {
      int i, j, tobeSorted;
      for (i = 1; i &lt; input.length; i++) {
        tobeSorted = input[i];
        j = i;
        while (j &gt; 0 &amp;&amp; input[j - 1] &gt; tobeSorted) {
          input[j] = input[j - 1];
          j--;
        }
        input[j] = tobeSorted;
      }
      //println(input);
      return input;
    }
  }
  
  /*
  
  Merge class, implements Sort interface
   # Last update: 25 October 2015 
  */
  
  
  class Merge implements Sort{
  
    Merge() {
    }
  
    int[] sortInteger(int[] input) {
      if (input.length &gt; 1) {
        // split array into two halves
        int[] left = leftHalf(input);
        int[] right = rightHalf(input);
  
        // recursively sort the two halves
        sortInteger(left);
        sortInteger(right);
  
        // merge the sorted halves into a sorted whole
        merge(input, left, right);
      }
      return input;
    }
  
    // Returns the first half of the given array.
    int[] leftHalf(int[] array) {
      int size1 = array.length / 2;
      int[] left = new int[size1];
      for (int i = 0; i &lt; size1; i++) {
        left[i] = array[i];
      }
      return left;
    }
  
    // Returns the second half of the given array.
    int[] rightHalf(int[] array) {
      int size1 = array.length / 2;
      int size2 = array.length - size1;
      int[] right = new int[size2];
      for (int i = 0; i &lt; size2; i++) {
        right[i] = array[i + size1];
      }
      return right;
    }
  
    void merge(int[] result, int[] left, int[] right) {
      int i1 = 0;   // index into left array
      int i2 = 0;   // index into right array
  
      for (int i = 0; i &lt; result.length; i++) {
        if (i2 &gt;= right.length || (i1 &lt; left.length &amp;&amp;
          left[i1] &lt;= right[i2])) {
          result[i] = left[i1];    // take from left
          i1++;
        } else {
          result[i] = right[i2];   // take from right
          i2++;
        }
      }
    }
  
  }
  
  /*
  
   Bubble class, implements Sort interface
   # Last update: 25 October 2015
   */
  
  
  class Bubble implements Sort {
  
    Bubble() {
    }
  
    int[] sortInteger(int[] input) {
      boolean swapped = true;
      int j = 0;
      int tmp;
      while (swapped) {
        swapped = false;
        j++;
        for (int i = 0; i &lt; input.length - j; i++) {                                       
          if (input[i] &gt; input[i + 1]) {                          
            tmp = input[i];
            input[i] = input[i + 1];
            input[i + 1] = tmp;
            swapped = true;
          }
        }
      }
      return input;
    }
  }
  
  /*
  
   Shell class, implements Sort interface
   # Last update: 25 October 2015 
   */
  
  
  class Shell implements Sort {
  
    Shell() {
    }
  
    int[] sequence = {59724292, 26544130, 11797391, 5243258, 2330349, 1035711, 460316, 204585, 90927, 40412, 17961, 7983, 3548, 1577, 701, 301, 132, 57, 23, 10, 4, 1};
    /*
    int number = 701;
     for(int i=0; i&lt;15; i++){    
     int newN = int(number*2.25);
     println(number);
     number =  newN;    
     }
     */
  
    int[] sortInteger (int[] input) {
      int size = input.length;
      int i, j, temp;
      for ( int s : sequence ) {
        i = s;
        while ( i &lt; size ) {
          temp = input[i];
          j = i-s;
          while ( j &gt;= 0 &amp;&amp; input[j] &gt; temp ) {
            input[j + s] = input[j];
            j -= s;
          }
          input[j + s] = temp;
          i ++;
        }
      }
      return input;
    }
  
  }
  
  /*
  
   QuickSort class, implements Sort interface
   # Last update: 26 October 2015 
   */
  
  
  class QuickSort implements Sort {
  
    QuickSort() {
    }
  
    int[] sortInteger(int[] input) {
      quickSort(input, 0, input.length-1) ;
      return  input;
    }
  
    public void quickSort(int arr[], int low, int high) 
    {
      int i = low, j = high;
      int temp;
      int pivot = arr[(low + high) / 2];
  
      /** partition **/
      while (i &lt;= j) 
      {
        while (arr[i] &lt; pivot)
          i++;
        while (arr[j] &gt; pivot)
          j--;
        if (i &lt;= j) 
        {
          /** swap **/
          temp = arr[i];
          arr[i] = arr[j];
          arr[j] = temp;
  
          i++;
          j--;
        }
      }
  
      /** recursively sort lower half **/
      if (low &lt; j)
        quickSort(arr, low, j);
      /** recursively sort upper half **/
      if (i &lt; high)
        quickSort(arr, i, high);
    }
  }
  </code></pre>