HackerRank Algorithm Challenge 1: Insertion sort This is my solution for HackerRank's first "Algorithm Challenge, Insertion Sort Part 1". The challenge is to sort the array from least to greatest, the input being an array in sorted order, except for the last entity, i.e. {2, 3, 4, 5, 6, 7, 8, 9, 1}

It works fine, but it's definitely not an optimal solution. Could anybody provide any insights on how I should look at it so as to optimize it? This is for learning purposes, so I can apply the same concepts to future code.

   static void insertionSort(int[] ar) {
          int i, j;
          int inserted = 0;
          i = ar[ar.length-1];

          for (j = ar.length-2; j &gt; -1; j--){
              if (ar[j] &gt; i){
                  ar[j+1] = ar[j];
                  printArray(ar);
              } else if (ar[j] &lt;= i){
                  ar[j+1] = i;
                  inserted = 1;
                  break;
              }   
          }

          if(inserted == 0){
              ar[0] = i;
          }

          printArray(ar);     
   }


This is the rest of the code, but it's preset and is already available: 

 static void printArray(int[] ar) {
     for(int n: ar){
        System.out.print(n+" ");
     }
       System.out.println("");
  }

  public static void main(String[] args) {
       Scanner in = new Scanner(System.in);
       int n = in.nextInt();
       int[] ar = new int[n];
       for(int i=0;i&lt;n;i++){
          ar[i]=in.nextInt(); 
       }
       insertionSort(ar);
   }
Two components in particular are unnecessary. This test:

        } else if (ar[j] &lt;= i){ 


is redundant. else means if (ar[j] &lt;= i), since the latter is the negation of the earlier if (ar[j] &gt; i).

And then, the inserted variable is used to track whether i was inserted within the loop. To simplify, I'd only do it outside the loop -- we can do this because j is still useful. (If you're not using j outside the loop, as in your original code, it's better -- safer, more readable -- style to declare it in the for statement.)

This is the heart of what you're doing:

static void insertionSort(int[] ar) {
    int i, j;
    i = ar[ar.length-1];

    for (j = ar.length-2; j &gt; -1; j--){
        if (ar[j] &gt; i){
            ar[j+1] = ar[j];
            printArray(ar);
        } else {
            break;
        }   
    }
    ar[j+1] = i;
    printArray(ar);
}


Or:

static void insertionSort(int[] ar) {
    int i = ar[ar.length-1];
    int j;
    for (j = ar.length-2; (j &gt;= 0) &amp;&amp; (ar[j] &gt; i); j--) {
        ar[j+1] = ar[j];
        printArray(ar);
    }
    ar[j+1] = i;
    printArray(ar);
}


There are some style quibbles, but that's the big stuff.  I'd take the printing out of it, except that the purpose of this function doesn't seem to be "perform an insertion sort", but rather "show how an insertion sort inserts an element".  I don't see any advantage to using a binary search, since that only helps you find the insertion point, and you still need to iterate over all elements > ar[i] to move their values.