How to quickly resort a list with only one changed value?

Question

Let's say I have a list of objects that are sorted by a specific field on that object. If one of the objects changes that property, its position in the sorted list would need to be updated.

What sorting algorithm or "tricks" could I use to very quickly sort this list, given that it falls out of sort only one item at a time?

The data structure is an array, and I have direct access to the index of the changed item.

I am using Scala for this, but any general tips or pointers would be helpful too.

Answer 1

If the list is sorted, you can simply remove the element you're about to change from the list, and after changing it, you could "binary-insert" it, no? That would take an average of log(n) steps.

If you can, change from an array to a java.util.TreeMap: both removal and insertion will be log(n) operations: which will be faster than your O(1) access + O(n) re-insertion solution using an array.

Answer 2

Depending on whether the new value is larger than, or smaller than, the previous one, you could "bubble" it in place.

The pseudo-code would look something like this:

if new value larger than old value
    then if new value is larger than next value in collection
        then swap the value with the next value
        iterate until value is not larger than next value
else if new value is smaller than previous value in collection
    then swap the value with the previous value
    iterate until value is not smaller than the previous value

Of course, a better way would be to use binary search.

First, locate the new spot in the collection where the element should be. Then, shift elements into place. If the new spot index is greater than the current spot index, you shift elements down one element, otherwise you shift them up. You shift elements starting from the spot you previously occupied, to the one you want to occupy. Then you store the value into the spot you found.

For instance, assume this collection:

 a   b   c   d   e   f   g   h   i    j
10  20  30  40  50  60  70  80  90  100

Then you want to change the value of the f element from 60 to 95.

First you figure out where it should be. Using binary search, we found that it should be between 90 and 100:

 a   b   c   d   e   f   g   h   i    j
10  20  30  40  50  60  70  80  90  100
                                   ^
                                   +- here

Then you shift elements from the current position down one element, like this:

 a   b   c   d   e   f   g   h   i    j
10  20  30  40  50  60  70  80  90  100  <-- from this
10  20  30  40  50  70  80  90  ??  100  <-- to this

And then you store the value into the ?? space, which gives you this formation

 a   b   c   d   e   g   h   i   f    j
10  20  30  40  50  70  80  90  95  100