Problem Set 1

Following is another implementation of insertion sort. If we feed an already sorted array to the following snippet will the algorithm execute a linear number of instructions? Insertion sort’s best case running time is linear (think running a single loop) and not quadratic.

    void sort(int[] input) {
        for (int i = 1; i < input.length; i++) {
            int key = input[i];
            for (int j = i - 1; j >= 0; j--) {
                if (input[j] > key) {
                    int tmp = input[j];
                    input[j] = key;
                    input[j + 1] = tmp;
                }
            }
        }
    }