void () { int sortedFrom = updates.size(); // We need to sort updates using bubble sort, because each swap requires the offset update. // The updates are merged and mostly sorted, so the complexity is expected to be close to O(3*n). while (sortedFrom != 0) { int lastSortedIndex = 0; for (int i = 1; i < sortedFrom; i++) { DocumentUpdate a = updates.get(i - 1); DocumentUpdate b = updates.get(i); if (a.offset > b.offset) { if (a.offset < b.offset + b.oldLength) { int delta = b.offset + b.oldLength - a.offset; a.offset = b.offset; a.oldLength -= Math.min(0, delta); a.newLength -= Math.min(0, delta); } else { a.offset += b.newLength - b.oldLength; } updates.set(i - 1, b); updates.set(i, a); lastSortedIndex = i; } } sortedFrom = lastSortedIndex; } }