// Insertion Sort 插入排序
//   时间：O(n^2) 最坏/平均
//         O(n) 最好（已有序）
//   空间：O(1)
//   稳定：是
#include "common/sort_test.hpp"

void insertion_sort(std::vector<int> &a)
{
    const int n = static_cast<int>(a.size());
    for (int i = 1; i < n; ++i)
    {
        const int key = a[i]; // 要插入的数
        int j = i - 1;
        while (j >= 0 && a[j] > key) // 比key大的放右边
        {
            a[j + 1] = a[j];
            --j;
        }
        a[j + 1] = key; // 空出来的位置放key
    }
}

int main(int argc, char **argv)
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    return sort_test::run("Insertion Sort", insertion_sort, argc, argv);
}