Indexed-heap sorting: correctness and uniform running-time bound
ProvedCLRS.HeapSortIndices.correctness_and_running_timeThere is one positive natural-number constant C, independent of all inputs and initial counters, such that for every initial heap, allocated key sequence, and natural length n, Lunjia Hu's indexed-heap sort terminates and returns a fresh allocated sequence. Its first n entries are a permutation of 0, ..., n−1 in nondecreasing order of their original keys. Previously allocated caller sequences and objects, and all collections, are preserved. The same completed call satisfies the original per-clock Budget n (2n), and the sum of its sort_steps, heap_comparisons, and heap_swaps increments is at most C·(1+n·(1+floor(log₂(n+1)))). Duplicate and negative keys and n=0 are allowed; no stability is asserted. The result describes sorted identifiers, not in-place sorting of input values. The counted work is the named source events, not every primitive operation, bit complexity, or wall-clock time. This theorem is derived from the existing published SortIndicesAnalysis.call contract; its proof is retained locally for review.
import Theorems.Thm_SortIndicesAnalysis_call set_option autoImplicit false open Algo2LeanGenerated
theorem CLRS.HeapSortIndices.correctness_and_running_time :
∃ C : Nat, 0 < C ∧
∀ (heap : Heap) (keys : SeqRef) (n : Nat), keys < heap.nextRef →
∃ after result,
Algo.sort_indices.sort_indices.Call heap (keys, (n : Int)) after result ∧
SortIndicesAnalysis.SortedPermutation (heap.read keys) (n : Int) (after.read result) ∧
SortIndicesAnalysis.Preserves heap after ∧
heap.nextRef ≤ result ∧ result < after.nextRef ∧
SortIndicesAnalysis.Budget (n : Int) (2 * n) heap after ∧
SortIndicesAnalysis.runtime (Heap.cost heap after) ≤
C * (1 + n * (1 + Nat.log2 (n + 1))) := by
sorry
Read-back
What the Lean code literally says, in plain math · GPT-6 (Codex, independent fresh-context agent)
Independent readback of CLRS.HeapSortIndices.correctness_and_running_time
There exists one positive natural constant C, chosen before all inputs, such that for every initial Heap, sequence reference keys, and natural number n, assuming only keys < heap.nextRef, there are a final heap after and a returned sequence reference result satisfying all the following together. C is independent of n, the keys and their magnitudes/order, all other heap contents, and all initial counter values. The final heap and result may depend on the inputs, but the same witnesses serve correctness, preservation, and both cost bounds.
The generated sort_indices procedure, called with (keys, n coerced to Int), has a finite execution returning result with heap after. Its Call relation requires such an execution under every suspended caller stack, with these same final witnesses; the transcript may depend on the stack. At an empty stack it terminates. The procedure constructs a min-priority queue, inserts identifiers, and extracts them into a separate output sequence.
Writing K(i) = heap.read keys i, the first n entries of after.read result are exactly a permutation of the integer identifiers 0,...,n-1, each occurring once, and their K-values are nondecreasing. Formally, one list of length n has that permutation and pairwise key-order property, and the output agrees with that list at every natural index below its length. The output contains identifiers rather than key values. Equal keys are permitted; no stable ordering among ties is specified by this sorting postcondition. That postcondition says nothing about negative output indices or indices at least n.
Every sequence reference below the original nextRef retains its entire integer-indexed contents, including the input keys and all aliases. Every object reference below the original nextObject retains its complete optional object value. The whole typed-collection store and nextCollection are unchanged. The sequence and object allocation counters cannot decrease. All named counters except sort_steps, heap_comparisons, and heap_swaps are unchanged. The result reference lies between the original nextRef (inclusive) and final nextRef (exclusive), so it is newly allocated and distinct from every previously allocated sequence. Preservation does not promise equality of the entire heap, preserve sequence/object slots outside the original allocated ranges, or give an upper bound on allocations.
Let L = floor(log2(n+1)). Budget bounds each final counter by its initial value plus: 2n for sort_steps, 4nL for heap_comparisons, and 2n(L+1) for heap_swaps; all other allowed increases are zero. runtime(Heap.cost heap after) is the sum, with unit weights, of the three named final-minus-initial natural-number counter differences. This sum is at most C*(1+n*(1+L)). Natural subtraction truncates at zero; no separate counter-monotonicity conjunct appears in the headline, although the generated updates only increment counters. The metric includes marked operations in nested heap calls and starts from the caller's existing counters. It measures loop-body ticks, instrumented key comparisons, and heap-swap ticks, not elapsed time, transcript length, every primitive operation, allocation cost, or integer bit complexity. No lower bound or tight Theta bound is asserted.
There is no finite-array-length hypothesis: Seq is the total function type Int -> Int, and references are naturals. n is nonnegative by type, keys may be arbitrary integers, and there is no initial priority-queue representation hypothesis. The allocation premise is satisfiable, so the theorem is not globally vacuous; heaps with nextRef = 0 have no eligible keys. n = 0 is included: the sorting-prefix condition is empty, but finite execution, fresh allocation, preservation, and zero measured counter cost are still required. The result is existential, not an explicit uniqueness theorem or a separate theorem quantifying over every execution. It establishes neither in-place key sorting nor a physical-memory bound nor correspondence with an external implementation or textbook pseudocode. No apparent type or contract contradiction was found by reading. HeadlineGoal.lean still ends with sorry, so this is a readback of an unproved target, not a proof or compilation certification.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.