wire / wire-format / mergesort

Mergesort

Divide-and-conquer sorting: split array in half, sort each half, merge. Guaranteed O(n log n) (best, average, worst). Stable (equal elements preserve order). Requires O(n) extra space. Used in Java's Arrays.sort() for objects, Python's sorted(), and external sorting.

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

aka: Mergesort

wire format

spec: Mergesort (von Neumann, 1945)

Divide-and-conquer sorting: split array in half, sort each half, merge. Guaranteed O(n log n) (best, average, worst). Stable (equal elements preserve order). Requires O(n) extra space. Used in Java's Arrays.sort() for objects, Python's sorted(), and external sorting.

fieldsizemeaning
DivideO(1)Split array into two halves.
Conquer2 * T(n/2)Recursively sort each half.
MergeO(n)Merge two sorted halves into one sorted array. Uses temporary buffer.
Bottom-up mergesortvariantIterative: start with size-1 runs, merge to size-2, size-4, etc. No recursion. Better cache locality.
TimsortvariantHybrid of mergesort and insertion sort. Finds natural runs, merges them. Used in Python and Java. O(n) for already-sorted data.

example:

00 00

Mergesort (placeholder)


provenance

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