Time and Space Complexity

時間計算量:

• 最良の場合: O(n)
  • 配列がすでにソートされている場合、挿入ソートはソート済みであることを確認するために1回だけパスを実行します。
• 平均および最悪の場合: O(n²)
  • 平均および最悪の場合、各要素についてソート済みの部分全体を比較して移動させる必要がある可能性があるため、2次時間がかかります。

空間計算量:

• O(1)
  • 挿入ソートは「インプレース（in-place）」アルゴリズムであり、入力サイズに比例した追加のメモリを必要としません。
  • ソートに使用される空間は、入力サイズに関係なく一定です。

まとめ:

• 挿入ソートは、小規模なデータセットや、ほぼソートされている配列に対して効率的です。
• 2次時間の計算量が必要なため、大規模なデータセットにはあまり適していません。
• 空間計算量は一定であり、どのような入力サイズに対してもメモリ効率が良いです。