insertion sort time complexity code example

Example 1: what is time complexity of insertion sort

Time Complexity is: 
If the inversion count is O(n), 
then the time complexity of insertion sort is O(n).

Some Facts about insertion sort:
1. Simple implementation: Jon Bentley shows a three-line C version, and a five-line optimized version[1]
2. Efficient for (quite) small data sets, much like other quadratic sorting algorithms
3. More efficient in practice than most other simple quadratic (i.e., O(n2)) 
algorithms such as selection sort or bubble sort
4. Adaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is O(kn)
when each element in the input is no more than k places away from its sorted position
5. Stable; i.e., does not change the relative order of elements with equal keys
6. In-place; i.e., only requires a constant amount O(1) of additional memory space
Online; i.e., can sort a list as it receives it

Example 2: insertion sort

// Por ter uma complexidade alta,
// não é recomendado para um conjunto de dados muito grande.
// Complexidade: O(n²) / O(n**2) / O(n^2)
// @see https://www.youtube.com/watch?v=TZRWRjq2CAg
// @see https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html

function insertionSort(vetor) {
    let current;
    for (let i = 1; i < vetor.length; i += 1) {
        let j = i - 1;
        current = vetor[i];
        while (j >= 0 && current < vetor[j]) {
            vetor[j + 1] = vetor[j];
            j--;
        }
        vetor[j + 1] = current;
    }
    return vetor;
}

insertionSort([1, 2, 5, 8, 3, 4])