Merging (in the sense of retaining some order property) is probably just as fast in static arrays as in lists. For large element sizes, you'd use an array of po

Merging (in the sense of retaining some order property) is probably just as fast in static arrays as in lists. For large element sizes, you'd use an array of pointers (requiring only one pointer per element in the data, doubling during the merge) and the pointer fiddling during the merge is about the same for either. For small elements, the list overhead alone is probably enough to make arrays faster. O(1) joining, splitting and removal are of course not beatable by contiguous data structures.