A data structure is presented for the Mergeable Dictionary abstract data type, which supports the operations Predecessor-Search, Split, and Merge on a collection of disjoint sets of totally ordered data. While in a typical mergeable dictionary (e.g. 2-4 Trees), the Merge operation can only be performed on sets that span disjoint intervals in keyspace, the structure here has no such limitation. A data structure which can handle arbitrary Merge operations in O(log n) amortized time in the absence of Split operations was presented by Brown and Tarjan . A data structure which can handle both Split and Merge operations in amortized time was presented by Farach and Thorup . In contrast, our data structure supports all operations, including Split and Merge, in amortized time, thus showing that interleaved Merge operations can be supported at no additional cost vis-à-vis disjoint Merge operations.