Building SortedArray: the Invariant and Adding

We are working with SortedArray<T extends Comparable<T>>, an array-backed list whose contract promises that reading it back from index 0 upward always gives a non-decreasing sequence. 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

The elements are always in sorted order: reading the array back from index 0 upward gives a non-decreasing sequence at all times, not just after a batch of operations finishes. 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(6) runs its own binary search over the occupied slots.

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

   0    1    2    3    4    5
┌────┬────┬────┬────┬────┬────┐
│  2 │  4 │  9 │ 13 │  _ │  _ │
└────┴────┴────┴────┴────┴────┘
   ↑    ↑         ↑    ↑
  low  mid      high size

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

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

   0    1    2    3    4    5
┌────┬────┬────┬────┬────┬────┐
│░ 2░│░ 4░│  9 │ 13 │  _ │  _ │
└────┴────┴────┴────┴────┴────┘
             ↑    ↑    ↑
          low,mid high size

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

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

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

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

It runs right-to-left from j = 4 down to 3: arr[4] = arr[3] copies 13 into the empty slot, giving [2, 4, 9, 13, 13].

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

Then arr[3] = arr[2] copies 9 into index 3, giving [2, 4, 9, 9, 13].

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

Finally arr[2] = 6 and size becomes 5, giving [2, 4, 6, 9, 13].

   0    1    2    3    4    5
┌────┬────┬────┬────┬────┬────┐
│  2 │  4 │  6 │  9 │ 13 │  _ │
└────┴────┴────┴────┴────┴────┘
             ↑
             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 closer to $n$ , driven by the shift, not the search, since for large $n$ the $lo g n$ comparisons are negligible compared to the $n$ moves.