import java.util.Arrays;
 
class InsertionSort {
 
  void insertionSort(int array[]) {
    int size = array.length;
 
    for (int step = 1; step < size; step++) {
      int key = array[step];
      int j = step - 1;
      while (j >= 0 && key < array[j]) {
        array[j + 1] = array[j];
        --j;
      }
      array[j + 1] = key;
    }
  }
  public static void main(String args[]) {
    int[] data = { 9, 5, 1, 4, 3 };
    InsertionSort is = new InsertionSort();
    is.insertionSort(data);
    System.out.println("Sorted Array in Ascending Order: ");
    System.out.println(Arrays.toString(data));
  }
}

aW1wb3J0IGphdmEudXRpbC5BcnJheXM7CgpjbGFzcyBJbnNlcnRpb25Tb3J0IHsKCiAgdm9pZCBpbnNlcnRpb25Tb3J0KGludCBhcnJheVtdKSB7CiAgICBpbnQgc2l6ZSA9IGFycmF5Lmxlbmd0aDsKCiAgICBmb3IgKGludCBzdGVwID0gMTsgc3RlcCA8IHNpemU7IHN0ZXArKykgewogICAgICBpbnQga2V5ID0gYXJyYXlbc3RlcF07CiAgICAgIGludCBqID0gc3RlcCAtIDE7CiAgICAgIHdoaWxlIChqID49IDAgJiYga2V5IDwgYXJyYXlbal0pIHsKICAgICAgICBhcnJheVtqICsgMV0gPSBhcnJheVtqXTsKICAgICAgICAtLWo7CiAgICAgIH0KICAgICAgYXJyYXlbaiArIDFdID0ga2V5OwogICAgfQogIH0KICBwdWJsaWMgc3RhdGljIHZvaWQgbWFpbihTdHJpbmcgYXJnc1tdKSB7CiAgICBpbnRbXSBkYXRhID0geyA5LCA1LCAxLCA0LCAzIH07CiAgICBJbnNlcnRpb25Tb3J0IGlzID0gbmV3IEluc2VydGlvblNvcnQoKTsKICAgIGlzLmluc2VydGlvblNvcnQoZGF0YSk7CiAgICBTeXN0ZW0ub3V0LnByaW50bG4oIlNvcnRlZCBBcnJheSBpbiBBc2NlbmRpbmcgT3JkZXI6ICIpOwogICAgU3lzdGVtLm91dC5wcmludGxuKEFycmF5cy50b1N0cmluZyhkYXRhKSk7CiAgfQp9