Java: how to sort an array each time an element is inserted

If it has to be an array, the best way to do it is to do a binary search to find the insertion point, move the higher value elements up by one place, then put the new element in the gap that opens up.

That moves on average half the array elements for each insert.

If you have the option of using a different data structure, I suggest a TreeMap in which the key is the Integer you are inserting, and the value is a count of the number of times that element has been inserted.

I suggest you to use a sorted collection like a SortedSet< Integer > (implementation class TreeSet).

Always sorted and remove duplicates.

If you absolutely want an int[], java.util.Arrays utility contains search and sort.

A Java array has fixed size, if you need to do removals and insertion you probably want a List (ArrayList or LinkedList)

Some alternatives:

1. A List; do a binary search for each insert to find the insertion point.

2. A List plus a Map; you keep in the map that tells you the (first) index of each integer in the list.

3. A List; do an insert plus a Collections.sort(list)

1 is the less straightforward, but most instructive. 2 is the most efficient in speed, but wastes space. 3 is the most straightforward and pragmatic.

How to sort an array each time an element is inserted

Do like this

 Arrays.sort(array);

Sorts the specified array of ints into ascending numerical order. The sorting algorithm is a tuned quicksort, adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993). This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance.

Read the java docs here.

and grow the item at runtime instead of Array use ArrayList.

Do like this in arrayList.

List<String> unsortList = new ArrayList<String>();
unsortList.add("111");
unsortList.add("333");
unsortList.add("222");

//before sort
System.out.println("ArrayList is unsort");
for(String temp: unsortList){
    System.out.println(temp);
}

//sort the list
Collections.sort(unsortList);

//after sorted
System.out.println("ArrayList is sorted");
for(String temp: unsortList){
    System.out.println(temp);
}

Arrays might not the best way of achieving what you are after, but this depends on what it is that you want from your class, and which methods it is important are fast.

To achieve what you are asking with an array, the best results you will be able to get are this (assuming the array is of infinite size / you are only storing a max number of integers):

• insertion: Worst Case: O(n), Average Case: O(n)
• removal: Worst Case: O(n), Average Case: O(n)
• getting element by index: Always: O(1)
• checking if element exists: Worst Case: O(log n) [Binary Search]

If this is the sort of efficiency and behaviour you are after, then here is the answer to your question:

So you are asking if this is efficient:

• Add new integer to end of the array: efficiency: O(1)
• Sort entire array: efficiency: O(n * log(n))

Total Efficiency: O(n * log(n))

There is a much more efficient way of doing it, this would involve doing the following:

• Perform Binary Search to find the point in the array where you need to insert the new integer. O( log n )
• Move everything to the right of this point along 1 (to make room in correct place). O(n)
• Insert new integer: O(1)

Total Efficiency: O( n )

Different data structures:

If this is not the kind of behaviour that you are after, then you could maybe look into some different kinds of data structures. For example, something based on trees, like TreeSet will give very different efficiency:

• insertion: O( log n )
• removal: O( log n )
• getting element by index: (not possible i believe? not familiar with this class's complete implementation)
• checking if element exists: O( log n )