Mostly sorted arrays: Insertion sort vs insert at sorted position

Question

I'm trying to figure out the most efficient way of maintaining a sorted ArrayList. I'm inserting items into the array one at a time. I'm deciding between two methods: inserting the item at the sorted position or inserting the item at the end of the end of the list and using insertion sort to sort the data because of its superior performance on mostly sorted arrays. I would think that inserting the item at the sorted position is more efficient, but I may be wrong.

Which method would be more efficient for this particular situation?

Answer 1

When inserting an item in the middle of the sorted array, you first need to find the correct location (e.g. via binary search), and you need to shift all the elements on the right of the insertion position one place to the right in order to make space.

• Comparisons: O(log n) per insertion, O(n log n) for all elements
• Movements: O(n) per insertion, O(n²) for all elements

When inserting an item at the end and then using an insertion sort pass, you do not need to know the insertion position up front. However, the insertion sort pass will compare all larger elements, and move all larger elements one step to the right.

• Comparisons: O(n) per insertion, O(n²) for all elements
• Movements: O(n) per insertion, O(n²) for all elements

Insertion pseudocode:

elements.add(newElement);  // at the end

// Move the new element forward in the array
// until it is at the correct position.
// This loop has O(n) average time complexity.
//
// Example ordering for ints:
//    boolean isOrdered(int a, int b) {
//      return a <= b;
//    }
int i = elements.size() - 1;
while (i > 0 && !isOrdered(elements[i - 1], elements[i])) {
  swap(elements, i - 1, i);
  i--;
}

This means using insertion sort instead of inserting the element at a position found through binary search involves the same number of movements, but requires far more comparisons. So inserting the new element directly at the sorted position is more efficient if the necessary comparisons are expensive, but both algorithms are essentially O(n²) (i.e. quadratic) over the course of all insertions.

If you want to be more efficient, you have to think about how you are using the data.

• If you don't need the items to be always sorted: First insert all elements, then sort them with an O(n log n) sorting algorithm.

• If you need to access the sorted items before all elements are available:

  • If you only need access to the maximal or minimal element, use a Heap.
  • If you need access to all current items in their order, use a self-balancing binary search tree, e.g. as implemented in Java's TreeMap.

Inserting elements into an ArrayList might still be the correct option, e.g. if the number of elements is very small.

Answer 2

There are two possibilities: One, you want your array always sorted after each new element. Two, you want to make multiple additions without having the array sorted, and then sort.

Forget what you heard about superior time for insertion sort for mostly sorted arrays if you want this fast. Look at the algorithm and find out why it is fast, and you'll see it doesn't work fast in your case. The expected number of operations is O (n*m) where n is the size of the already sorted array, and m the number of items added. Plus lots of time is wasted to make the first n items sorted when they are already sorted. Your array isn't "almost sorted" because the last m items could belong anywhere.

To add a single item and then sort, you can do just the very last pass of insertion sort. You changed n to n+1, and the first n items are sorted. Insertion sort would spend lots of time to make sure they are really sorted, which is wasted.

To add m items and then sort, that can be done easily in O (n + m log m) instead of O (n*m) which insertion sort would take. It's simple. Copy the m items into a separate array and sort them in O (m log m). Then move everything where it belongs: Let i = n-1, j = m-1, k = n+m-1. As long as i >= 0 and j >= 0 either set array [k] = array [i] and set i = i-1, or set array [k] = newarray [j] and set j = j-1; in either case set k = k-1. If j < 0 you quit, if i < 0 then you copy newarray [0] to new array [j] to array [0] to array [j].

Answer 3

If you know your list is almost sorted, you should try to sort it by insertion. But before you start to look for the correct position at which the element must be inserted, compare the element to be inserted with the last element of the sorted list: you will probably just have to insert the current element at the end of the list. For the few cases you actually have to find the correct position, you lost your time to compare two elements, which is a O(1) operation.

So in the worst case, this approach is O(1) + O(n log n) = O (n log n) for inserting an element, but in most cases it will be done in O(1).