Building SortedArray: the Invariant and Adding

We are working with SortedArray<T extends Comparable<T>>, an array-backed list that keeps its elements in sorted order. Here is its skeleton:

public class SortedArray<T extends Comparable<T>> {
  private T[] arr;
  private int size;

  @SuppressWarnings("unchecked")
  public SortedArray() {
    arr = (T[]) new Comparable[10];
    size = 0;
  }

  private void grow() {
    // doubles the backing array, same as DynamicArray
  }

  // insertionPoint and add go here
}

Solution

An invariant is a condition on the data structure’s state that holds at all times, not just after a batch of operations finishes. Here the condition is that reading the array back from index 0 upward gives a non-decreasing sequence. Every method that changes the array’s contents has to leave it sorted before it returns, because the next call might be a binary search that depends on the array being sorted.

Exercise

Implement insertionPoint(T value). It returns value’s own index if value is already present, or the index it should be inserted at otherwise.

private int insertionPoint(T value) {
  // TODO: implement this method
}

Solution

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;
}

Exercise

Implement add(T value) using insertionPoint.

public void add(T value) {
  // TODO: implement this method
  // Assume grow() is available to double the backing array if needed.
  // Make use of the insertionPoint() method to find where to insert the new value.
}

Solution

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];
  }
  arr[i] = value;
  size++;
}

Solution

insertionPoint(33) runs its own binary search over the occupied slots.

Step 1: low=0, high=3, mid=1.

   0    1    2    3    4    5
┌────┬────┬────┬────┬────┬────┐
│ 11 │ 25 │ 42 │ 58 │  _ │  _ │
└────┴────┴────┴────┴────┴────┘
   ↑    ↑         ↑    ↑
  low  mid      high size

arr[1]=25 is less than 33, so set low = mid + 1 = 2.

Step 2: low=2, high=3, mid=2.

   0    1    2    3    4    5
┌────┬────┬────┬────┬────┬────┐
│░11░│░25░│ 42 │ 58 │  _ │  _ │
└────┴────┴────┴────┴────┴────┘
             ↑    ↑    ↑
          low,mid high size

arr[2]=42 is greater than 33, so set high = mid - 1 = 1. Now low > high, so the range is empty and low is now 2: insertionPoint(33) returns 2, since 33 belongs between 25 and 42.

   0    1    2    3    4    5
┌────┬────┬────┬────┬────┬────┐
│░11░│░25░│ 42 │ 58 │  _ │  _ │
└────┴────┴────┴────┴────┴────┘
             ↑
      insertion point

The shift starts with j = size = 4, ready to copy arr[3] into arr[4].

   0    1    2    3    4    5
┌────┬────┬────┬────┬────┬────┐
│ 11 │ 25 │ 42 │ 58 │  _ │  _ │
└────┴────┴────┴────┴────┴────┘
                  ↑    ↑
                 j-1   j

It runs right-to-left from j = 4 down to 3: arr[4] = arr[3] copies 58 into the empty slot, giving [11, 25, 42, 58, 58].

   0    1    2    3    4    5
┌────┬────┬────┬────┬────┬────┐
│ 11 │ 25 │ 42 │ 58 │ 58 │  _ │
└────┴────┴────┴────┴────┴────┘
                       ↑
                       j

Then arr[3] = arr[2] copies 42 into index 3, giving [11, 25, 42, 42, 58].

   0    1    2    3    4    5
┌────┬────┬────┬────┬────┬────┐
│ 11 │ 25 │ 42 │ 42 │ 58 │  _ │
└────┴────┴────┴────┴────┴────┘
                  ↑
                  j

Finally arr[2] = 33 and size becomes 5, giving [11, 25, 33, 42, 58].

   0    1    2    3    4    5
┌────┬────┬────┬────┬────┬────┐
│ 11 │ 25 │ 33 │ 42 │ 58 │  _ │
└────┴────┴────┴────┴────┴────┘
             ↑
             i

Solution

The shift dominates. Finding the insertion point is a binary search, about $lo g n$ comparisons. But if the new value is smaller than everything already in the array, the insertion point is 0, and the shift has to move every one of the $n$ existing elements one slot right, which is proportional to $n$ . So add’s worst-case cost is proportional to $n$ , driven by the shift, not the search.