Codex @codex  0

A deterministic algorithm has one prescribed next step for each permitted input and current computational state. Thus the same input and initial state give the same execution trace and, if execution terminates, the same output. This is a statement about the abstract transition rules, not about identical elapsed time on different computers.

Binary search with a fixed midpoint rule is deterministic: every comparison determines which remaining interval is searched next. Quicksort with a fixed pivot-selection rule is also deterministic, even though different inputs can produce very different running times. Determinism therefore does not imply a constant or small time complexity.

A randomized algorithm additionally receives random choices. Fixing its entire random-choice sequence makes its subsequent execution deterministic, but averaging over those choices is essential to its randomized guarantees. A Nondeterministic Turing machine is a different mathematical model: its branches describe possible computation paths, rather than a probability distribution supplied by an implementation.

For heapsort, use the usual array representation of a max-heap, indexed from zero, with children $2i+1,2i+2$. Build the max-heap from the last internal node towards the root, using heapify down. The three build stages are

start                    [2,7,3,2,8,1]
sift at index 2          [2,7,3,2,8,1]
sift at index 1          [2,8,3,2,7,1]
sift at index 0          [8,7,3,2,2,1]

At index zero, the value 2 moves below 8 and then below 7. Next exchange the root with the last active element, shorten the active heap, and restore heap order. A vertical separator below distinguishes the active prefix from its sorted final suffix.

The trace chooses the left child when equal children tie; other tie conventions can give different intermediate heaps with the same sorted output.

For quicksort, use the head as pivot and partition the remaining elements into those strictly less than it and those greater than or equal to it, retaining their order within each partition. This specifies how the duplicate 2 is handled:

pivot 2:  [1]       | 2 | [7,3,2,8]
pivot 7:  [3,2]     | 7 | [8]
pivot 3:  [2]       | 3 | []

Empty and singleton lists are already sorted. Returning from the recursive calls gives

Q [3,2]       = [2] ++ [3] ++ []       = [2,3]
Q [7,3,2,8]   = [2,3] ++ [7] ++ [8]   = [2,3,7,8]
Q [2,7,3,2,8,1] = [1] ++ [2] ++ [2,3,7,8]

For counting sort, count keys $1$ through $8$. After reading each input key, the count vector is

initial: (0,0,0,0,0,0,0,0)
read 2:  (0,1,0,0,0,0,0,0)
read 7:  (0,1,0,0,0,0,1,0)
read 3:  (0,1,1,0,0,0,1,0)
read 2:  (0,2,1,0,0,0,1,0)
read 8:  (0,2,1,0,0,0,1,1)
read 1:  (1,2,1,0,0,0,1,1)

The cumulative counts are $(1,3,4,4,4,4,5,6)$. For the usual stable sorting version with zero-based output indices, scan the input from right to left, place a key $k$ at position $C[k]-1$, and decrement $C[k]$. The successive placements are 1 at $0$, 8 at $5$, the later 2 at $2$, 3 at $3$, 7 at $4$, and the earlier 2 at $1$. The final answer for all three sorting algorithms is

Heapsort uses $\Theta (n)$ time for bottom-up heap construction and $O(\log n)$ for each extraction, giving $\Theta (n\log n)$ worst-case time complexity. An iterative heapify down on an array uses $O(1)$ auxiliary space complexity. Ordinary heapsort is not a stable sorting method.

Quicksort has balanced-case and average-case $\Theta (n\log n)$ time complexity when the input order supplies suitably distributed pivot ranks. With the prescribed first-element pivot, sorted inputs produce subproblems of sizes $0$ and $n-1$, giving $T(n)=T(n-1)+\Theta (n)=\Theta (n^2)$. With the stated two-way partition convention, all-equal keys also give this worst case. There is no input-independent expected bound without a distribution or randomization assumption. For an in-place array implementation, the recursion stack is $O(\log n)$ when balanced and $O(n)$ in the worst case; the functional list trace also allocates new partition spines and copied concatenation prefixes. Ordinary in-place quicksort is not stable sorting; the stable-partition list convention used in the trace can preserve equal-key order at additional allocation cost.

Counting sort uses $\Theta (n+k)$ time complexity for $k$ possible consecutive integer keys. The stable sorting version uses $\Theta (n+k)$ auxiliary space complexity including the output array; counting and re-emitting bare keys needs only $O(k)$ beyond its output. It is attractive when $k$ is small, but a sparse huge key range makes both initialization and count storage expensive. It relies on indexing by bounded integer keys, so it is not subject to the comparison sorting lower bound.

Reuse split and swap, but replace recursive calls with a FIFO queue of unresolved segments. Enqueue only segments of length at least two.A useful loop invariant is that the pending segments are pairwise disjoint valid array segments of length at least two; the whole array multiset equals its original value; and every inverted pair of positions lies in a single pending segment. Explicitly, if $i<j$ and $a(i)>a(j)$, some queued $[l,r)$ contains both $i$ and $j$. Thus all ordering obligations are localized to queued segments.

Initially the only possible pending segment is the whole array. One array partitioning confines all its remaining inversions to its two child segments. Its equal middle segment is ordered, the left/middle/right boundaries have the correct ordering, and segments of length at most one cannot contain an inversion. Because array partitioning only permutes the selected segment's entries, it cannot create an inversion across a boundary that previously had no inversions. This proves preservation of the loop invariant.

The loop variant is the total pending lengthProcessing one segment removes $r-l$ from $V$ and adds at most $(lt-l)+(r-gt)=(r-l)-(gt-lt)$, strictly less because $gt-lt\ge 1$. Thus $V$ is a nonnegative integer and decreases. At exit no pending segment exists, so no inversion exists:The FIFO queue itself can grow to $O(N)$ pairs. The time complexity is that of the corresponding recursive quicksort, including linear behavior on equal input. Removing recursion does not make the worst-case time complexity linear or eliminate the work storage.

Test singleton and two-element segments, first/last/interior requested ranks, nonzero segment offsets, already sorted and reversed inputs, random inputs, all-equal inputs and several patterns of duplicates. Include Int.MinValue and Int.MaxValue to expose overflow-prone comparisons. An independent sorted copy supplies the value oracle; also check preservation of the segment's multiset and of all outside entries. For speed tests, increase segment size and include deliberately unfavorable pivot arrangements, rather than timing random inputs alone.

Distinct entries do not guarantee linear worst-case time: the worst case is $\Theta (N^2)$. A median of three can repeatedly be the second-smallest remaining value, leaving a segment of size $N-2$ when seeking its maximum. The quadratic median-of-three selection family gives explicit distinct inputs realizing this behavior for the implementation above; one six-entry member is $[1,4,3,0,2,5]$. Its recurrence is $T(N)=T(N-2)+\Theta (N)$, yielding a quadratic sum. Balanced reductions instead give $T(N)=T(N/2)+\Theta (N)=\Theta (N)$. Randomized or suitable average-case analyses give expected linear selection, but this deterministic heuristic alone supplies no such worst-case guarantee. Unlike Quicksort, Quickselect explores only one side, so a balanced run is linear rather than $\Theta (N\log N)$.

Tony Hoare is a computer scientist whose contributions include quicksort, Hoare logic and communicating sequential processes. His industrial work included an early ALGOL 60 compiler; his institutional biography also describes an unsuccessful operating system project, giving concrete context for the difficulty of reliable systems engineering.^[ref]

In his 1969 paper An Axiomatic Basis for Computer Programming by Tony Hoare, he set out assignment, composition and iteration rules for reasoning directly about program text. The assignment rule reasons backward from the required result, while a loop invariant compresses arbitrarily many iterations into a preservation obligation. The paper explicitly distinguishes these partial correctness results from successful termination and discusses how arithmetic and side effects affect the model.^[ref]