Sorting Timestamped Messages (iOS)
If both new and old messages are sorted it's basically a merge of two sorted arrays, similar to the merge step in merge sort. It can be done O(n + m) time. I'd suggest you to look into how that's implemented.