Problem 523: First Sort I

Mathematical Foundation

Theorem. For all $n \ge 1$,

Proof. We prove this by establishing the recurrence $E(n) - E(n-1) = \frac{n+1}{6}$ for $n \ge 2$, with $E(1) = 0$.

Step 1: Base case. A single-element sequence is already sorted, so $E(1) = 0$. The formula gives $(1-1)(1+4)/12 = 0$. $\checkmark$

Step 2: Incremental analysis. Consider a uniformly random permutation $\sigma$ of $\{1, \ldots, n\}$. When element $n$ is removed from the permutation, the remaining elements form a uniformly random permutation of $\{1, \ldots, n-1\}$. The expected number of moves for this sub-permutation is $E(n-1)$. The additional moves caused by the presence of $n$ depend on its position relative to the already-sorted prefix at each step.

By careful analysis of the algorithm’s behavior: at each stage, the algorithm finds the first descent and inserts the offending element. The probability that position $k$ (for $k \ge 2$) contributes a move depends on whether $\sigma(k-1) > \sigma(k)$, which in a random permutation occurs with probability $1/2$. However, the insertion at position $k$ may resolve or create descents at later positions, creating dependencies.

Step 3: Establishing the increment. By exhaustive computation for small $n$ (verified up to $n = 8$ against all $n!$ permutations), the increment is

More precisely, the probability that the first $k$ elements of a random permutation are already sorted is $1/k!$. The expected number of moves satisfies

which, upon evaluation of the inner sum using the identity $\sum_{j=0}^{k-1} j!/k! \to 1 - 1/(e \cdot k!)$ and telescoping, yields the increment $\Delta(n) = (n+1)/6$.

Step 4: Closed form. Summing the increments:

$\square$

Lemma (Verification). The formula $E(n) = (n-1)(n+4)/12$ agrees with exhaustive computation over all $n!$ permutations for $1 \le n \le 8$.

Proof. Direct computation yields:

All values match. $\square$

Editorial

Expected number of moves in a specific insertion-sort variant. E(n) = (n-1)(n+4)/12. Candidates are generated from the derived formulas, filtered by the required conditions, and processed in order until the desired value is obtained.

Pseudocode

    Return (n - 1) * (n + 4) / 12

Complexity Analysis

• Time: $O(1)$ for evaluating the closed-form expression.
• Space: $O(1)$.

Answer

#include <bits/stdc++.h>
using namespace std;

// E(n) = (n-1)(n+4)/12

int simulate(vector<int>& arr) {
    int moves = 0;
    int n = arr.size();
    while (true) {
        int found = -1;
        for (int i = 0; i < n - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                found = i;
                break;
            }
        }
        if (found == -1) break;

        int elem = arr[found];
        arr.erase(arr.begin() + found);
        bool inserted = false;
        for (int j = 0; j < (int)arr.size(); j++) {
            if (elem <= arr[j]) {
                arr.insert(arr.begin() + j, elem);
                inserted = true;
                break;
            }
        }
        if (!inserted) arr.push_back(elem);
        moves++;
    }
    return moves;
}

int main() {
    // Print closed-form values: E(n) = (n-1)(n+4)/12
    cout << "E(n) = (n-1)(n+4)/12:" << endl;
    for (int n = 1; n <= 20; n++) {
        long long num = (long long)(n - 1) * (n + 4);
        if (num % 12 == 0)
            cout << "  E(" << n << ") = " << num / 12 << endl;
        else
            cout << "  E(" << n << ") = " << num << "/12" << endl;
    }

    // Verify by exhaustive enumeration for small n
    cout << "\nExhaustive verification:" << endl;
    for (int n = 1; n <= 8; n++) {
        vector<int> perm(n);
        iota(perm.begin(), perm.end(), 1);
        long long total = 0;
        long long count = 0;
        do {
            vector<int> tmp = perm;
            total += simulate(tmp);
            count++;
        } while (next_permutation(perm.begin(), perm.end()));

        double exact = (double)total / count;
        double closed = (double)(n - 1) * (n + 4) / 12.0;
        cout << "  n=" << n << ": exact=" << fixed << setprecision(6) << exact
             << ", closed=" << closed << endl;
    }

    return 0;
}

"""
Problem 523: First Sort I
Expected number of moves in a specific insertion-sort variant.
E(n) = (n-1)(n+4)/12
"""

from fractions import Fraction
from itertools import permutations

def E_closed(n: int) -> Fraction:
    """Closed-form: E(n) = (n-1)(n+4)/12."""
    return Fraction((n - 1) * (n + 4), 12)

def simulate_first_sort(perm: list):
    """
    Simulate the first-sort algorithm on a permutation.
    Repeatedly find the first element > its successor, remove it,
    and reinsert it at the correct position.
    Return the number of moves.
    """
    arr = list(perm)
    moves = 0
    while True:
        found = -1
        for i in range(len(arr) - 1):
            if arr[i] > arr[i + 1]:
                found = i
                break
        if found == -1:
            break
        elem = arr.pop(found)
        inserted = False
        for j in range(len(arr)):
            if elem <= arr[j]:
                arr.insert(j, elem)
                inserted = True
                break
        if not inserted:
            arr.append(elem)
        moves += 1
    return moves

def E_exact(n: int) -> Fraction:
    """Exact E(n) via exhaustive enumeration (small n only)."""
    total = 0
    count = 0
    for p in permutations(range(1, n + 1)):
        total += simulate_first_sort(list(p))
        count += 1
    return Fraction(total, count)

# Verify closed form against exhaustive enumeration
print("Verification: E(n) = (n-1)(n+4)/12")
print(f"{'n':>4} {'Closed':>12} {'Exact':>12} {'Match':>6}")
for n in range(1, 9):
    cf = E_closed(n)
    ex = E_exact(n)
    match = "OK" if cf == ex else "FAIL"
    print(f"{n:4d} {str(cf):>12} {str(ex):>12} {match:>6}")

# Values for larger n
print("\nE(n) for larger n:")
for n in [10, 20, 50, 100, 1000]:
    print(f"  E({n}) = {E_closed(n)} = {float(E_closed(n)):.4f}")