挿入ソート（Insertion Sort）は、配列を部分的に整列させながら全体をソートしていくアルゴリズムである。既に整列された部分に対して、次の要素を適切な位置に挿入することで、徐々に整列範囲を広げていく。

アルゴリズムの流れ

1. 最初の要素を「整列済み」とみなす。
2. 次の要素を取り出し、整列済み部分の末尾から先頭に向かって比較を行う。
3. 取り出した要素が比較対象より小さい場合、その位置に挿入するため、それより大きい要素を右にずらす。
4. この操作を配列の最後まで繰り返す。

計算量の分析

時間計算量

最悪ケース（降順の配列）では、各要素について最大でi回の比較と移動が必要となる。したがって、総比較回数は1 + 2 + … + (n−1) = n(n−1)/2となり、時間計算量はO(n²)となる。

空間計算量

追加メモリは一時変数のみを使用するため、空間計算量はO(1)である。

特徴

利点

• 実装が単純で理解しやすい。
• 小規模データやほぼ整列済みのデータに対して効率的。
• 安定ソートであり、等価な要素の相対順序が保たれる。

欠点

• 大規模かつ無秩序なデータに対しては非効率。
• O(n²)の時間計算量のため、実用的な高速ソートには不向き。

二分挿入ソートによる改善

挿入位置の探索を線形探索から二分探索に置き換えることで、比較回数をO(log i)に削減できる。ただし、要素のシフト操作は依然としてO(i)かかるため、全体の時間計算量は変わらずO(n²)となる。定数倍の高速化は期待できるが、漸近的な改善はない。

コード例（C言語）

void insertion_sort(int arr[], int n) {
    for (int i = 1; i < n; ++i) {
        int current = arr[i];
        int pos = i - 1;
        while (pos >= 0 && arr[pos] > current) {
            arr[pos + 1] = arr[pos];
            --pos;
        }
        arr[pos + 1] = current;
    }
}

実際の問題への応用

例1：極端値を除いた平均値（LeetCode 1491）

double average(int* salary, int size) {
    insertion_sort(salary, size);
    long total = 0;
    for (int i = 1; i < size - 1; ++i)
        total += salary[i];
    return (double)total / (size - 2);
}

例2：両端5%をトリムした平均（LeetCode 1619）

double trimMean(int* arr, int size) {
    insertion_sort(arr, size);
    int remove = size / 20;
    long sum = 0;
    for (int i = remove; i < size - remove; ++i)
        sum += arr[i];
    return (double)sum / (size - 2 * remove);
}

例3：k個選んだときの最小スパン（LeetCode 1984）

int minimumDifference(int* scores, int n, int k) {
    insertion_sort(scores, n);
    int min_gap = INT_MAX;
    for (int i = 0; i + k <= n; ++i)
        min_gap = fmin(min_gap, scores[i + k - 1] - scores[i]);
    return min_gap;
}