wire / wire-format / 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.
aka: Quicksort
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.
| field | size | meaning |
|---|---|---|
| Partition | O(n) | Rearrange array so elements < pivot are left, > pivot are right. Pivot in final position. |
| Recurse | O(log n) depth | Recursively sort left and right partitions. |
| Pivot selection | strategy | First/last element (bad for sorted data). Random (expected O(n log n)). Median-of-three (good in practice). |
| Three-way partition | variant | Partition into < pivot, = pivot, > pivot. Handles duplicates efficiently (O(n) for all-equal input). |
| Introsort | variant | Quicksort + heapsort fallback. Switches to heapsort if recursion depth exceeds 2*log2(n). Used in C++ std::sort. |
example:
00 00
Quicksort (placeholder)
agent: curl -H 'accept: application/json' wire.phall.io/wire-format/quicksort
or /wire-format/quicksort.json