Insertion Sort

void isort(int *array, int size)
{
    int i, j, current;
    for (i = 1; i < size; i++) {
        current = array[i];
        for (j = i; j > 0; j--) {
            if (array[j - 1] > current)
                array[j] = array[j - 1];
            else
                break;
        }
        array[j] = current;             // current is not index -> swap(current, j) cause ERROR
    }
}

Best:
O(n) — when the array is already sorted, there will be no shifting, only run the outer loop for n-1 time

Avg:
O(n2) — in average case, every time when we try to insert an item, it require half time shifting. That is still n2 time.

Worst:
O(n2) — when the array is reversely sorted, it requires shifting all the previous items. 1 + 2 + 3 + … + n-1 is n2 time.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License