Answer: Invariants

Question: Write invariants at the indicated space in the following functions.

void
insertionSort(int *arr, int n) {
    for(int i = 0; i < n; i++) {
        // INVARIANT: ???
        int temp = arr[i];
        int j = i - 1;
        while(j >= 0 && arr[j] > arr[i]) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;
    }
}

Answer: The first i elements of the initial array are in sorted order in the first i elements of the current array.