Is there a way to merge two Python deques in O(1)?
Double linked lists can be merged in O(1), and deque is the implementation of a double linked list. However, from the documentation I do not see a way to do efficiently merge two deques. The a.extend(b) and a += b mentioned in this question actually iterate over all the elements of b, so the time complexity is O(len(b)) and not O(1).
Nope. deques aren't plain doubly linked lists. They're a linked list of blocks of multiple values (on the CPython reference interpreter, each block can contain up to 64 values), where only the start and end blocks may be incomplete; none of the blocks may be sparse. So it has to fill in the end block of the left hand side, which means the next block gets filled from a mix of two blocks, etc.
Beyond that, since there is no such thing as destructive iteration in Python (nothing language supported anyway), it can't actually transfer the blocks even if the end block of the left, and the start block of the right were full. Copies must happen, block ownership can't be transferred.
I'm posting this as a separate answer rather than continuing to converse-in-comments under ShadowRanger's good answer. :)
ShadowRanger points out, correctly, that one of deque's invariants is that the blocks in the middle of the list are always 100% full. Therefore, if you had two deques like
X = (. . . 1) (2 3 4 5) (6 7 . .) [3 blocks, 7 elements]
Y = (8 9 A B) (C D E .) [2 blocks, 7 elements]
there would be literally no way to concatenate them in O(1) time while preserving order, because deque's invariant does not permit you to express the result as
X+Y = (. . . 1) (2 3 4 5) (6 7 . .) (8 9 A B) (C D E .) [invalid]
You would have to adjust the positions of all the elements in one or the other of the deques, either like this:
X+Y = (. . . 1) (2 3 4 5) (6 7 8 9) (A B C D) (E . . .) [adjusted elements 8 thru E]
or like this:
X+Y = (. 1 2 3) (4 5 6 7) (8 9 A B) (C D E .) [adjusted elements 1 thru 7]
Those are simple pointer swaps, so they're fast; but there are still O(n) of them.
However, suppose you pass in two deques whose alignments just happen to coincide?
X = (. . . 1) (2 3 4 5) (6 7 . .) [3 blocks, 7 elements]
Y = (. . 8 9) (A B C D) (E . . .) [3 blocks, 7 elements]
X+Y = (. . . 1) (2 3 4 5) (6 7 8 9) (A B C D) (E . . .) [can be done in O(1)]
Here, after we manually append items 8 and 9, it does become physically possible to pilfer the entire tail of the right-hand deque in O(1). And deque can detect this possibility in O(1); and manually appending those first few items takes O(block size) = O(1). So yes, it is physically possible for concatenating two deques to be implemented in O(1) time, under special circumstances which do not always hold.
However, you would have to call that operation something other than x += y or x.extend(y). Those two operations are specified not to modify their right-hand operand. The standard deque from collections does not provide any "destructive" operation like that. (But, if it existed, I would expect it to be named splice.)
You can see the implementation of deque's += operator (as implemented in CPython) here.