Use binary search to find the correct position. O(lgn) comparisons. private static int[] insert(int[] a, int val) { if(val 0; i--){ a[i] = a[i - 1]; } a[0] = val; return a; } else if(val > a[a.length - 2]){ a[a.length - 1] = val; return a; } else return insert(a, val, 0, a.length - 1); } private static int[] insert(int[] a, int val, int start, int end) { int mid = (end - start)/2 + start; if(a[mid] mid + 1; i--){ a[i] = a[i - 1]; } a[mid + 1] = val; return a; } else if(val >= a[mid + 1]){ //search right side return insert(a, val, mid+1, end); } else { //search left side return insert(a, val, start, mid-1); } }