Why can a sorted linked-list merge run in O(1) extra space when the array version cannot?

## What "extra space" means here Auxiliary (extra) space is what an algorithm allocates *beyond* its input and its output. Counting it correctly is the whole question, and it is where the two structures diverge. Take two per-server event logs, each already ordered by timestamp, and merge them into one timeline. ## Why the list merge is O(1) In a linked structure, the ordering *is* the set of links. Each node stores an event and a reference to whoever comes next. To produce a merged order you do not have to move a single event payload — you rewrite the links so that walking from the new head visits the events in timestamp order. The machinery needed for that is fixed: a cursor into each input, a tail reference for the result, and (usually) one sentinel node. Three or four references, regardless of whether each log holds ten entries or ten million. No allocation happens per element, so auxiliary space is O(1) and the merge does zero copying of payloads. This is also why the standard advice "merging sorted sequences needs a scratch buffer" is an array habit, not a law. On a list it is simply false. ## Why the array merge is not A contiguous array stores order positionally: the element at index i comes before the element at index i+1, and there is no link to rewrite. To place the earliest event first in the output you must *write* it to output position 0. If the output is one of the inputs, that write destroys whatever lived there. Concretely: the first input's earliest event is often not the global earliest, so the very first write of an in-place attempt overwrites a value that has not yet been compared, and it is gone — arrays give you no second copy of it. So the one-pass merge writes into a destination of size n+m and reads from both inputs, which is O(n+m) auxiliary space. In-place merge algorithms for arrays do exist; they work by rotating or block-swapping runs rather than by streaming, and they buy their constant space with substantially more complexity and a worse constant factor (some variants pay an extra logarithmic factor in time). They are real, and they are not what anyone writes by default — which is the point: on arrays constant-space merging is an exotic technique, and on lists it is the *only* thing that happens. ## Two directions people get wrong **"O(1) extra space means lists use less memory."** No. It means the *merge* allocates nothing proportional to n. The list already spent one reference per element to exist at all, so for the same events a linked structure occupies more total memory than two arrays did. The merge is cheap in space; the structure is not. **"O(1) extra space means the inputs survive."** No. The merge is destructive by construction: the nodes it relinks are the input nodes. After it returns, walking from an old input head no longer yields that log — it yields a suffix of the merged timeline, interleaved with events from the other server. That is often exactly what you want when combining streams. When it is not, you must clone the nodes first, and that clone is O(n) time and O(n) space — the cost you thought you had avoided has just moved. ## Where the array version is nevertheless the right call The asymptotic score favors the list, and real hardware often does not. A merge over arrays reads two contiguous runs and writes one, a pattern prefetchers handle almost perfectly. A merge over lists chases references that may sit anywhere in memory; every step risks a cache miss, and the miss dominates the comparison by orders of magnitude. For a large one-off merge of bulk log data, copying into contiguous storage, merging there, and rebuilding can beat the elegant constant-space relink, and paying O(n) extra space to do it is a defensible engineering choice. The constant-space list merge wins clearly when the data is *already* in linked form for other reasons — nodes are shared with other structures, elements are spliced and unspliced constantly, or references to individual nodes are held elsewhere and must stay valid. Those are the conditions that made it a list in the first place, and they are the ones to name when you defend the choice. ## Saying it precisely "Merging two sorted lists is O(n+m) time and O(1) auxiliary space, destructive to both inputs; merging two sorted arrays in one pass is O(n+m) time and O(n+m) auxiliary space unless you use a specialized in-place merge." Every clause in that sentence is load-bearing, and dropping the word *auxiliary* or the word *destructive* is what turns a correct answer into a misleading one.