Insertion Sort

• Time : O(n^2)
• Space : O(1)

c++

// best : O(n) time | O(1) space
// avg : O(n^2) time | O(1) space
// worst : O(n^2) time | O(1) space
vector<int> insertionSort(vector<int> array) {
    int n = array.size();
    for(int i = 0; i < n; i++) {
        int j = i;
        while(j > 0 and array[j-1] > array[j]) {
            swap(array[j], array[j-1]);
            j--;
        }
    }
    return array;
}