Sorting

AP Computer Science A· difficulty 3/5

int[] a = {1, 2, 3, 4, 5};
for (int i = 1; i < a.length; i++) {
  int v = a[i];
  int j = i - 1;
  while (j >= 0 && a[j] > v) {
    a[j+1] = a[j];
    j--;
  }
  a[j+1] = v;
}

On an already-sorted array, insertion sort has time complexity:

A
$O(n)$
check_circle
B
$O(n log n)$
C
$O(1)$
D
$O(n^2)$

Explanation

On sorted input the inner while loop never iterates, giving O(n).

Want 10 more like this — adaptive to your weak spots?

Practice 10 like thisarrow_forward Predict my AP score

Related questions