Partner – Moderne – NPI EA (cat=Spring Boot)
announcement - icon

Refactor Java code safely — and automatically — with OpenRewrite.

Refactoring big codebases by hand is slow, risky, and easy to put off. That’s where OpenRewrite comes in. The open-source framework for large-scale, automated code transformations helps teams modernize safely and consistently.

Each month, the creators and maintainers of OpenRewrite at Moderne run live, hands-on training sessions — one for newcomers and one for experienced users. You’ll see how recipes work, how to apply them across projects, and how to modernize code with confidence.

Join the next session, bring your questions, and learn how to automate the kind of work that usually eats your sprint time.

Course – Black Friday 2026 – NPI EA – main – before_post_content
announcement - icon

Yes, we're now running our Black Friday Sale. All Courses are 33% off until 1st December, 2026 at 17:00 Romania time:

>> EXPLORE ACCESS NOW

Course – Black Friday 2026 – NPI – main – before_post_content
announcement - icon

Yes, we're now running our Black Friday Sale. All Courses are 33% off until 1st December, 2026 at 17:00 Romania time:

>> EXPLORE ACCESS NOW

1. Overview

The usage of arrays is very common in programming languages. Inserting and removing elements from an array of numbers is a basic operation we often need. Inserting an element into a sorted array of numbers is a special case of an array insertion.

Let’s see how to insert a number into a sorted array of numbers efficiently.

2. Introduction to Problem

To make inserting a number into a sorted array efficient, we need to minimize the number of position shifts and comparisons. We can achieve this by searching for the insertion index using binary search. Then, shift the elements to the right to make space for the new element.

For example, given that sortedArray is a sorted integer array:

int[] sortedArray = new int[] { 4, 55, 85, 100, 125 };

We want to add a new element 90 to the array. The algorithm should insert the number after 85 and before 100 in an efficient manner:

int[] expcetedArray = new int[] { 4, 55, 85, 90, 100, 125 };

3. Solution

The solution involves two steps. The first is to find the insertion index for the new number. The most efficient way of doing that is with a binary search. Once the index is found, we increase the size of the array by 1, shift the elements from the index up to the end to the right, and insert the new element at the calculated index:

public static int[] insertInSortedArray(int[] arr, int numToInsert) {
    int index = Arrays.binarySearch(arr, numToInsert);

    if (index < 0) {
        index = -(index + 1);
    }

    int[] newArray = new int[arr.length + 1];

    System.arraycopy(arr, 0, newArray, 0, index);

    newArray[index] = numToInsert;

    System.arraycopy(arr, index, newArray, index + 1, arr.length - index);

    return newArray;
}

Arrays.binarySearch(arr, element) returns the element insert index using binary search. The binarySearch() method returns a positive element insert index if the element is found in the array arr. If the element is not found in the array arr, it returns the negation of insert index plus one. Hence, if the returned index value is less than 0, we add 1 and negate it to get the insertion index.

We create a new array of size 1 more than that of the original array and insert the value at the calculated index in the new array. Then, to replicate the shifting of elements from the insert index to the end of the array, we copy values from the original array to the new array.

System.arraycopy() is used to efficiently copy the array before and after the insert index.

Let’s validate our code with a test case:

@Test
void givenSortedArray_whenElementInserted_thenArrayRemainsSorted() {
    int[] sortedArray = new int[] { 4, 55, 85, 100, 125 };
    int[] expcetedArray = new int[] { 4, 55, 85, 90, 100, 125 };
    int valueToInsert = 90;
    int[] resultArray = insertInSortedArray(sortedArray, valueToInsert);
    assertThat(expcetedArray).isEqualTo(resultArray);
}

The test case inserts new element 90 in the array sortedArray. Our insertion method insertInSortedArray() returns the result in the array resultArray. The test case matches the expected output array expectedArray with the result array resultArray. Since the test case passes successfully, it validates our array insertion logic.

Similarly, we can implement the solution for an array of numeric wrapper classes like Integer[], Double[], etc. The only change would be in array type, as both binarySearch() and arrayCopy() methods work with the wrapper class arrays.

4. Time Complexity

As discussed earlier, there are two steps in the solution. The binary search for calculating the insertion index has a time complexity of O(log n), and shifting of the elements has a complexity of O(n). Hence, the overall complexity of the solution is O(n).

5. Conclusion

In this article, we learned that a number can be inserted in a sorted array efficiently in Java by having two steps, i.e., binary search for figuring out the element insert index and right shifting of elements from the element insert index.

The code backing this article is available on GitHub. Once you're logged in as a Baeldung Pro Member, start learning and coding on the project.
Partner – Moderne – NPI EA (tag=Refactoring)
announcement - icon

Modern Java teams move fast — but codebases don’t always keep up. Frameworks change, dependencies drift, and tech debt builds until it starts to drag on delivery. OpenRewrite was built to fix that: an open-source refactoring engine that automates repetitive code changes while keeping developer intent intact.

The monthly training series, led by the creators and maintainers of OpenRewrite at Moderne, walks through real-world migrations and modernization patterns. Whether you’re new to recipes or ready to write your own, you’ll learn practical ways to refactor safely and at scale.

If you’ve ever wished refactoring felt as natural — and as fast — as writing code, this is a good place to start.

Course – Black Friday 2026 – NPI EA – main – after_post_content

announcement - icon

Yes, we're now running our Black Friday Sale. All Courses are 33% off until 1st December, 2026 at 17:00 Romania time:

>> EXPLORE ACCESS NOW

Course – Black Friday 2026 – NPI – main – after_post_content

announcement - icon

Yes, we're now running our Black Friday Sale. All Courses are 33% off until 1st December, 2026 at 17:00 Romania time:

>> EXPLORE ACCESS NOW