Great question! Let's break this down clearly—insertion sort's runtime is directly tied to the number of inversions in the array (each inversion corresponds to a shift operation during sorting). The total time complexity is Θ(I + n), where I is the total number of inversions. So our goal is to build an array where I = Θ(n^(7/4)).

Simple Construction: Blockwise Reverse-Sorted Arrays #

Here's a straightforward, easy-to-verify structure:

• Split the array into m = n^(1/4) contiguous blocks, each of size s = n^(3/4) (note that m * s = n^(1/4) * n^(3/4) = n, so this covers the entire array).
• Within each block: Arrange elements in strict reverse order (e.g., the k-th block could be [s*k, s*k - 1, ..., s*(k-1) + 1]).
• Between blocks: Ensure all elements in block i are strictly smaller than all elements in block j for i < j (so blocks are ordered increasingly overall).

Why This Hits Θ(n^(7/4)) Time #

Let's calculate the total inversions:

• Block-internal inversions: A reverse-sorted block of size s has s*(s-1)/2 ≈ s²/2 inversions. Since s = n^(3/4), this is Θ(n^(3/2)) per block.
• Cross-block inversions: Zero. Because blocks are ordered increasingly, there are no pairs where an element in an earlier block is larger than an element in a later block.
• Total inversions: Multiply the per-block inversions by the number of blocks: n^(1/4) * Θ(n^(3/2)) = Θ(n^(1/4 + 3/2)) = Θ(n^(7/4)).

Insertion sort will spend Θ(n^(7/4)) time processing the inversions, plus Θ(n) time for the rest of the operations—so overall runtime is Θ(n^(7/4)).

Alternative Construction: Prefix Reverse-Sorted, Suffix Sorted #

If you prefer a simpler linear structure instead of blocks, this works too:

• Take the first t = Θ(n^(7/8)) elements and arrange them in strict reverse order.
• The remaining n - t elements are sorted in strict increasing order, and every element in the suffix is larger than every element in the prefix.
• Total inversions come only from the prefix: t*(t-1)/2 ≈ t²/2 = Θ(n^(7/4)), which again gives us the desired time complexity.

Key Takeaway #

The core idea is to control the total number of inversions in the array. By avoiding full reverse order (which gives Θ(n²) inversions) and instead limiting inversions to a subset of the array (either in blocks or a prefix), we can dial in the exact inversion count needed to hit Θ(n^(7/4)) runtime for insertion sort.

内容的提问来源于stack exchange，提问作者Nir