Adding in Order

DynamicArray.add is simple: put the new element at the end and increase the size. A SortedArray cannot do that. Append 3 to [1, 4, 7] and you get [1, 4, 7, 3], which is no longer sorted. The invariant is broken.

To preserve order, add has to put the new element in its correct place. For add(3) on [1, 4, 7], the correct place is between 1 and 4. We have to open a gap, a free slot, and drop the new element into it:

1. Find the index where the element belongs.
2. Shift everything from that index rightward by one to create a free slot.
3. Drop the element into the freed slot.

The Insertion Point

Step 1 is a search. We can use binary search (since the invariant guarantees the array is sorted) and adjust it to return the index where the value belongs, the insertion point.

Here is the code that finds the insertion point:

private int insertionPoint(T value) {
  int low = 0;
  int high = size - 1;
  while (low <= high) {
    int mid = low + (high - low) / 2;
    int cmp = arr[mid].compareTo(value);
    if (cmp == 0) {
      return mid;
    } else if (cmp < 0) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return low;
}

A few things are different from in the original binary search. First the surface level changes: this one is an instance method on SortedArray, so it reads the field arr and searches 0 to size - 1 rather than the whole backing array, and it compares with compareTo because T is bounded by Comparable. It is also private, since the insertion point is an implementation detail the client does not need.

The changes that matter are the two return statements. When the value is found we return mid, its actual index, instead of true in the original. And when the loop ends without finding it, we return low instead of -1.

Why is low the right index? Track what low means as the loop runs. It starts at 0. The only line that moves it is low = mid + 1, and we run that line only when arr[mid] is smaller than the value. So every time low moves, it moves past an element we have just confirmed is smaller than the value, and past everything to the left of that element too, since the array is sorted. In other words, low always sits just after the elements we know are smaller. When the range finally empties, everything below low is smaller than the value and everything from low up is not. That is the insertion point.

Here is that search for where 5 belongs in a SortedArray holding [1, 4, 7, 9], backed by an array of capacity 6. The backing array arr is bigger than size, exactly as it is for DynamicArray; there are two free slots at indices 4 and 5, marked _.

  0   1   2   3   4   5
┌───┬───┬───┬───┬───┬───┐
│ 1 │ 4 │ 7 │ 9 │ _ │ _ │
└───┴───┴───┴───┴───┴───┘
  ↑   ↑       ↑   ↑
  L   M       R size

The search only ever looks at 0 through size - 1, so those free slots never enter into it. The L, M, R are low, mid, high. The middle element 4 is smaller than 5, so the insertion point must be further right:

  0   1   2   3   4   5
┌───┬───┬───┬───┬───┬───┐
│░1░│░4░│ 7 │ 9 │ _ │ _ │
└───┴───┴───┴───┴───┴───┘
          ↑   ↑   ↑
         L,M  R size

The shaded ░ cells are the ones we have confirmed are smaller than 5.

Now the middle element 7 is larger than 5, so the insertion point must be to the left. But there is nothing to the left of 7 that we have not already confirmed is smaller, so the range empties and the loop ends. low is index 2, which is the insertion point for 5.

  0   1   2   3   4   5
┌───┬───┬───┬───┬───┬───┐
│░1░│░4░│ 7 │ 9 │ _ │ _ │
└───┴───┴───┴───┴───┴───┘
          ↑
   insertion point

Shift and Insert

Now that we can find the insertion point, add can open the gap and drop the value in.

public void add(T value) {
  if (size == arr.length) {
    grow();
  }
  int i = insertionPoint(value);
  for (int j = size; j > i; j--) {
    arr[j] = arr[j - 1];  // shift larger elements one slot right
  }
  arr[i] = value;  // drop the new element into the gap
  size++;
}

The insertion point for 5 was index 2, so everything from index 2 onward has to slide right by one to open a gap.

  0   1   2   3   4   5
┌───┬───┬───┬───┬───┬───┐
│ 1 │ 4 │ 7 │ 9 │ _ │ _ │
└───┴───┴───┴───┴───┴───┘
              ↑   ↑
             j-1  j

It slides into the nearer free slot, index 4, the one the diagrams above already showed as _.

The loop runs right-to-left, from j = size down to i + 1. First we copy 9 from index 3 into that free slot at index 4:

  0   1   2   3   4   5
┌───┬───┬───┬───┬───┬───┐
│ 1 │ 4 │ 7 │ 9 │ 9 │ _ │
└───┴───┴───┴───┴───┴───┘
                  ↑
                  j

Then we copy 7 from index 2 into index 3. Notice the duplicate 7: the original is still at index 2 and will be overwritten:

  0   1   2   3   4   5
┌───┬───┬───┬───┬───┬───┐
│ 1 │ 4 │ 7 │ 7 │ 9 │ _ │
└───┴───┴───┴───┴───┴───┘
              ↑
              j

The gap at index 2 is now safe to fill. We drop 5 in, and the array is sorted again:

  0   1   2   3   4   5
┌───┬───┬───┬───┬───┬───┐
│ 1 │ 4 │ 5 │ 7 │ 9 │ _ │
└───┴───┴───┴───┴───┴───┘
          ↑
          i

Cost

add does two things, and they cost very different amounts.

Finding the spot is a binary search, so it is about $\log n$ comparisons, the count we worked out earlier in the chapter. That part is cheap.

The shifting is not cheap. The loop copies one slot per element from the insertion point to the end. If the new value is larger than everything already there, the insertion point is the end and the loop copies nothing. If it is smaller than everything already there, the insertion point is 0 and the loop copies all $n$ elements. So in the worst case the shift touches every element, which is $n$ steps, and that is much more work than the $\log n$ comparisons of the search.

That is a real change from DynamicArray. There, add writes one slot at the end and is done, no matter how big the array is. Keeping the array sorted makes searching much faster. It also makes adding slower.