Note that re-sorting an array after making a constant number of changes can be done in O(n) and will usually be very fast in practice. Insertion sort will do it, as will Timsort and similar algorithms.