wire / wire-format / 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.
aka: Mergesort
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.
| field | size | meaning |
|---|---|---|
| Divide | O(1) | Split array into two halves. |
| Conquer | 2 * T(n/2) | Recursively sort each half. |
| Merge | O(n) | Merge two sorted halves into one sorted array. Uses temporary buffer. |
| Bottom-up mergesort | variant | Iterative: start with size-1 runs, merge to size-2, size-4, etc. No recursion. Better cache locality. |
| Timsort | variant | Hybrid 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)
agent: curl -H 'accept: application/json' wire.phall.io/wire-format/mergesort
or /wire-format/mergesort.json