Inserting an element into an array in sorted order

You can use the Arrays or Collections binarySearch function to get the position to insert the new value at, you will need to shift all elements from this position (if any) to the right

int position = Math.abs(Collections.binarySearch(sortedList, key)) - 1;

public class InsertInSortedArray {
        public static void main(String[] args) {
            int arr[] = {5, 6, 9, 11};
            Arrays.sort(arr);
            int k = 7;
            int index = findIndexToBeInserted(arr, k, 0, arr.length - 1);
            ArrayList<Integer> al = new ArrayList<>();
            for (int i : arr)
                al.add(i);

            al.add(index, k);
            for (int i : al)
                System.out.println(i);
        }

    private static int findIndexToBeInserted(int[] arr, int k, int start, int end) {
            if (k == 0)
                return 0;

            int mid = (start + end) / 2;

            if (k > arr[mid] && k < arr[mid + 1])
                return mid + 1;

            if (arr[mid] < k)
                return findIndexToBeInserted(arr, k, mid + 1, end);

            return findIndexToBeInserted(arr, k, start, mid - 1);
        }
    }

There is an issues in your for loop

for(i=0;i<arr.length-1;i++){}

It should iterate up to i<arr.length

for(i=0;i<arr.length;i++){}

Here

arr[k+1]=arr[k];

You're overriding every next array element with a previous value. You should probably reverse your loop and move from the end of the array, shifting all elements forward until you find the right spot, i.e.:

public static void insert(int val, int[] arr) {
    for(int i = arr.length - 1; i > 0; i--) {
        if (arr[i] == 0) continue; // skip last elements to avoid array index out of bound
        arr[i + 1] = arr[i];       // shift elements forward
        if (arr[i] <= val) {       // if we found the right spot
            arr[i] = val;          // place the new element and
            break;                 // break out the loop
        }
    }
    System.out.println(Arrays.toString(arr));
}

Another way of solving is by using List and collections.sort method.

List<Integer> list = new ArrayList<Integer>(); 
  for (int i = 0; i < arr.length; i++) { 
  list.add(arr[i]); 
  } 
  list.add(val);

  Collections.sort(list);

 int[] result = list.stream().mapToInt(Integer::intValue).toArray();
 System.out.println(Arrays.toString(result));

Hope this solutions helps.

Java Code,

public static void insertElementInSortedArr(int a[], int val) {

        int n[] = new int[a.length + 1];
        int j = 0;
        boolean isAdded = false;
        for (int i = 0; i < a.length; i++) {
            if (a[i] < val) {
                n[j] = a[i];
                j++;
            } else {
                if (!isAdded) {
                    n[j] = val;
                    j = j + 1;
                    isAdded = true;
                }
                n[j] = a[i];
                j = j + 1;
            }
        }
    }

completely unclear how an insert function should work without knowing the number of fields already occupied?

public static void insert( int n, int occupied, int[] array ) {
  if( n >= array[occupied - 1] )
    array[occupied] = n;
  else
    for( int i = 0; i < array.length; i++ ) {
      int n1 = array[i];
      int n2 = array[i + 1];
      if( n1 > n || n1 < n && n2 >= n ) {
        if( n1 > n ) i--;
        System.arraycopy( array, i + 1, array, i + 2, occupied - i - 1 );
        array[i + 1] = n;
        break;
      }
    }
}

called from Your example above:

…
arr[3]=11;
int occupied = 4;
insert( 7, occupied, arr );  // [5, 6, 7, 9, 11, 0]

unchecked bust with ArrayIndexOutOfBoundsException if occupied >= array.length

To be honest, the array in question is not really sorted like this: [0, 0, 5, 6, 9, 11].
It is a "zero tailed" array: [5, 6, 9, 11, 0, 0].
So to insert a value into that array it needs to know how many elements occupied are. In case when you provide this value into a method it would have O(log n) complexity. Otherwise, it needs to implement counting inside the inserting method.

/**
* @throws ArrayIndexOutOfBoundsException when the array is full and the value to be inserted is greater than the last element
*/
private static void insertToZeroTailedArray(int val, int[] arr) {
    // an O(n) operation to count occupied elements
    int elementsCount = 0;
    for (int i = arr.length - 1; i >= 0; i--) {
        if (arr[i] != 0) {
            elementsCount = i + 1;
            break;
        }
    }

    // binarySearch returns a negative position to insert if the value was not found
    int index = Arrays.binarySearch(arr, 0, elementsCount, val);
    if (index != 0) {
        int pos = index < 0
                ? -index - 1 // val not found, it is need to be inserted at (-index)-1 position
                : index;     // val found but we are going to insert it again

        // shift the array to right and drop last element because of the array bounds
        System.arraycopy(arr, pos, arr, pos + 1, arr.length - pos - 1);
        arr[pos] = val;
    } else {
        // the case when value is found at 0 position
        System.arraycopy(arr, 0, arr, 1, arr.length - 1);
        arr[0] = val;
    }
}

An alternative way to do what you need with O(log n) complexity for a really sorted array:

private static void insertToReallySortedArray(int val, int[] arr) {
    int index = Arrays.binarySearch(arr, val);
    if (index != 0) {
        int pos = index < 0 ? -index - 1 : index;
        System.arraycopy(arr, pos, arr, pos + 1, arr.length - pos - 1);
        arr[pos] = val;
    } else {
        System.arraycopy(arr, 0, arr, 1, arr.length - 1);
        arr[0] = val;
    }
}

Based on this great answer.

You could use the arrays.sort() functionality to insert a value into a new array then sort it. It solves the issue in a roundabout way. For example

    int num = 10;
    int array[] = {6, 7, 8};
    int copy_array[] = new int[array.length + 1];
    for (int i = 0; i < array.length; i++) {
        copy_array[i] = array[i];
    }
    copy_array[copy_array.length - 1] = given_number;
    Arrays.sort(copy_array);

this solution maybe help you or notice for in a specific your problem
in a sorted array , a search operation is performed for the possible position of the givin element by using Binary search , and then an insert operation is performed followed by shifting the elements to the right way .

 public class InsertElmSort {
   
    // Inserting a key elements in arr[] of gevin.
    //capacity . n is current size of arr[] . 
    //this function return n + 1 if insertion is successful,
    //else return n .
   static int insertSorted(int arr[] , int n , int key , int capacity ) { 
         int i;
           for(i = n - 1 ; (i >= 0 && arr[i] > key); i-- ) {
                arr[i + 1] = arr[i];

                //the way 1   
              //arr[i] = key; 

          }

          //the way 2 instead of above way 1 by out the for loops block
        arr[i + 1] = key;
                     
         // can not access more elements if n is already 
         //more than or equal capacity
        if(n >= capacity) {
          return n;
         
        }  
       
        return (n + 1); 
             
       }

    
 public static void main (String args[]) {
   int arr[] = new int[20];
   arr[0] = 1 ; 
   arr[1] = 3 ;  
   arr[2] = 5; 
   arr[3] = 6;   
   arr[4] = 9; 
   arr[5] = 11;
   
   int n = 6; 
   int capacity = arr.length;       
   int key = 7;

   System.out.print("Before the insertion: "); 
     for (int i = 0; i < n; i++) {
          System.out.print(arr[i] + " ");
       }

    //call function to inserting key .
    n = insetSorted(arr , n , key , capacity);
    System.out.print("\n After the insertion: ")
       for(int i = 0; i < n ; i++) {
         System.out.print(arr[i] + " ");

        }


     }

       
}