Auto comment: topic has been updated by dragonslayerintraining (previous revision, new revision, compare).

Check this

proof for splay trees(?)
"Starting with a collection of $$$n$$$ singleton sets, we show that any sequence of $$$n - 1$$$ meld operations can be carried out in $$$O(n \log n)$$$ time to produce a single ordered set of at most $$$n$$$ items."

The $$$O(n \log n^2)$$$ bound is somewhat know from the Educational Codeforces Round 35. Back then, I gave a similar proof here. It is definitely less know than the sparse segment tree technique which doesn't work with operation 4. Another downside of these sparse segment trees is that they use $$$O(n \log n)$$$ memory ($$$O(n)$$$ memory is possible if you only store nodes with an even number of children, but then the implementation gets tricky. This is even less known.).

In the paper "Design of Data Structures for Mergeable Trees", the similar (but harder) problem of maintaining heap ordered dynamic trees is discussed and the same bounds are achieved ($$$O(n \log n)$$$ for only merges and $$$O(n \log n^2)$$$ for merges + splits). They also conjectures that splay trees achieve $$$O(n \log n)$$$ runtime while allowing splits.

Join-based merging with treaps needs $$$\Omega(n \log n^2)$$$ time on the following instance:

1. Let $$$n = k^2$$$ and consider the $$$k$$$ sets $$$\{1, \dots, k\}$$$ , $$$\{k+1, \dots, 2\cdot k\}, \dots, \{n-k+1, \dots, n\}$$$.
2. If we perform the worst-case sequence for split-join mering described in the blog on these sets, then we have $$$O(k)$$$ merge operations resulting in $$$\Omega(k \log k)$$$ split operations inside the join-based merge. Each of these split operations operates on a tree of size at least $$$k$$$, so every such split takes $$$\Omega(\log k)$$$ time. Hence we have $$$O(k)$$$ merge operations taking $$$\Omega(k \log k^2)$$$ in total.
3. After merging all the sets, we perform $$$O(k)$$$ split operations to get back to the initial $$$k$$$ sets.
4. Repeating this (2) and (3) $$$k$$$ times gives us $$$O(k^2) = O(n)$$$ operations running in $$$\Omega(k^2 \log k^2) = \Omega(n \log n^2)$$$ time.

This instance shows that finger search properties on their own are not sufficient for achieving $$$O(n \log n)$$$ time. Splay trees only use $$$O(n \log n)$$$ time on this class of instances. I suspect that weighting nodes by the distance to their neighbours in the set also allows you to achieve $$$O(n \log n)$$$ runtime.

Benchmark showing the $$$\log n^2$$$ behaviour for join-based merge with treaps. The benchmark counts recursive calls to split, join and merge (instead of using wall time) to reduce the noise from cache effects.

Sorry for the necroposting, but there is a recent paper that achieves all operations in $$$\mathcal{O}(\log U)$$$ amortized time, where $$$[1, U]$$$ is the universe set. So, using keys in range $$$[1, n]$$$, any sequence of $$$n$$$ such operations can be applied in $$$\mathcal{O}(n \log n)$$$ time.