InsertBinarSort

import java.util.*;
public class InsertionSort {
    public static int [] sort(int [] a, int j){
        int nb = j;
        int nm = 0;
        int p = a[j];
        while (nm < nb){
            int mid = (nm + nb) / 2;
            if (p < a[mid]){
                nb = mid;
            }
            else{
                nm = mid + 1;
            }
        }
        for (int i = nm; i <= j; i++){
            int hm =a [i];
            int k = i - 1;
            while ( k >= nm && a[k] > hm){
                a[k + 1] = a[k];
                a[k] = hm;
                k--;
            }
        }

        return a;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter a number: ");
        int n = sc.nextInt();
        int [] a = new int[n];
        a[0] = sc.nextInt();
        for (int i = 1; i < n; i++){
            a[i] = sc.nextInt();
            a = sort(a, i);
        }
        for (int i = 0; i < n; i++){
            System.out.print(a[i] + " ");
        }

    }

}