wire / wire-format / quicksort

Quicksort

Divide-and-conquer sorting: pick a pivot, partition into elements < pivot and > pivot, recurse. Average O(n log n), worst case O(n^2) (sorted input with naive pivot). In-place (O(log n) stack). Not stable. Randomized pivot gives expected O(n log n). Three-way partition (Dutch national flag) handles duplicates.

wire-format kind wire-format status standard verification verified tier B wire-format@1

aka: Quicksort

wire format

spec: Quicksort (Hoare, 1961)

Divide-and-conquer sorting: pick a pivot, partition into elements < pivot and > pivot, recurse. Average O(n log n), worst case O(n^2) (sorted input with naive pivot). In-place (O(log n) stack). Not stable. Randomized pivot gives expected O(n log n). Three-way partition (Dutch national flag) handles duplicates.

fieldsizemeaning
PartitionO(n)Rearrange array so elements < pivot are left, > pivot are right. Pivot in final position.
RecurseO(log n) depthRecursively sort left and right partitions.
Pivot selectionstrategyFirst/last element (bad for sorted data). Random (expected O(n log n)). Median-of-three (good in practice).
Three-way partitionvariantPartition into < pivot, = pivot, > pivot. Handles duplicates efficiently (O(n) for all-equal input).
IntrosortvariantQuicksort + heapsort fallback. Switches to heapsort if recursion depth exceeds 2*log2(n). Used in C++ std::sort.

example:

00 00

Quicksort (placeholder)


provenance

agent: curl -H 'accept: application/json' wire.phall.io/wire-format/quicksort or /wire-format/quicksort.json