title: Improving the runtime of Insertion sort
body: <p>Just to practice and improve my programming skills I decided to solve the questions on InterviewStreet. I decided to start off using simple InsertionSort (I expected it to be simple).
  <a href="https://www.interviewstreet.com/challenges/dashboard/#problem/4e90477dbd22b" rel="nofollow">https://www.interviewstreet.com/challenges/dashboard/#problem/4e90477dbd22b</a>
  I am able to get correct answers. However the runtime is a problem. The max allowed runtime for the test cases is 5s. However I am going slightly overboard.
  I used a few tricks (like removing something out of code. Storing the result of str.lenght() etc). However I am still slightly overboard.</p>
  
  <p>The current runtimes for the ten test cases are:</p>
  
  <p>1   Passed  Success             0.160537</p>
  
  <p>2   Passed  Success             0.182606</p>
  
  <p>3   Passed  Success             0.172744</p>
  
  <p>4   Passed  Success             0.186676</p>
  
  <p>5   Failed  Time limit exceeded.    5.19279</p>
  
  <p>6   Failed  Time limit exceeded.    5.16129</p>
  
  <p>7   Passed  Success             2.91226</p>
  
  <p>8   Failed  Time limit exceeded.    5.14609</p>
  
  <p>9   Failed  Time limit exceeded.    5.14648</p>
  
  <p>10  Failed  Time limit exceeded.    5.16734</p>
  
  <p>I am not aware what the test cases are.
  Kindly help me improve the runtime.
  Thank you.</p>
  
  <pre><code>import java.util.Scanner;
  import java.io.*;
  //import java.io.BufferedWriter;
  //import java.io.FileInputStream;
  //import java.io.FileOutputStream;
  
  public class Solution {
      public static int[] A=new int[100001]; 
      public static int swap=0;
      public static void InsertionSort(int n){
      for (int i=1; i&lt;=n; i++){    
          for (int var=i; var&gt;0; var--){
              if (A[var]&lt;A[var-1]){
                  int temp=A[var-1];
                  A[var-1]=A[var];
                  A[var]=temp;
                  swap++;
              }
              else {
                  break;
              }
          }
      }
      }
  
  
      public static void main(String[] args) throws IOException  {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  
          String str = br.readLine();
          int number_of_cases =Integer.parseInt(str);
          int counter;
          int [] spacearray = new int[100000];
  
          for (int j=0; j&lt;number_of_cases; j++){
              swap=0;
              str = br.readLine();
              int arraylength = Integer.parseInt(str);
  
              str = br.readLine();
              counter=0;
              int strlen=str.length();
              for (int i=0; i&lt;strlen-1; i++){
                  if (str.charAt(i) == ' '){
                      spacearray[counter]=i;
                      counter++;
                  }
              }
              spacearray[counter]=strlen;
  
              A[0]=Integer.parseInt(str.substring(0, spacearray[0]));
              for (int i=1; i&lt;=arraylength-1; i++){
                  A[i] = Integer.parseInt(str.substring(spacearray[i-1]+1,spacearray[i]));
              }
  
              InsertionSort(arraylength-1);
  
              System.out.println(swap);
          }
      }
  }
  </code></pre>