C++ High Performance/

...

/

Time Complexity of Insertion Sort

Time Complexity of Insertion Sort

Learn about the time complexity of the insertion sorting algorithm.

We'll cover the following...

Insertion sort analysis

Let's try to find the time complexity of the following sorting algorithm:

Press + to interact
void insertion_sort(std::vector<int>& a) {
  for (size_t i = 1; i < a.size(); ++i) {
    auto j = i;
    while (j > 0 && a[j-1] > a[j]) {
      std::swap(a[j], a[j-1]);
      --j; 
    }
  } 
}

The input size is the size of the array. The running time could be estimated approximately by looking at the loops that iterate over all elements. First, there is an outer loop iterating over n−1n - 1 elements . The inner loop is different: the first time we reach the while-loop, j is 1 and the loop only runs one iteration. On the next iteration, j starts at 2 and decreases to 0. For each iteration in the outer for-loop, the inner loop needs to do more and more work. Finally, j starts at n−1n - 1, which means that we have, in the worst case, executedswap() 1+2+3 ...