Sorting Timestamped Messages (iOS)

Question

An app I'm building professionally includes rudimentary text messaging. It allows users to send from the phone, and it polls for new messages (I know, yikes. Push notifications are a future task) with variable frequency for new messages from other users.

Part of its functionality is of course keeping messages in date-sorted order, and each message has a timestamp on it. I came up with two sorting implementations and I was curious as to which one would be more efficient.

Implementation 1:

for (Message* message in messages) {
 [self.backingMessages addObject:message];
}
NSSortDescriptor* sortingDescriptor = [NSSortDescriptor sortDescriptorWithKey:@"fullTimestamp" ascending:YES];
[self.backingMessages sortUsingDescriptors:@[sortingDescriptor]];

Implementation 2:

for (Message* message in messages) {
 NSInteger insertionPoint = [self.backingMessages indexOfObject:message inSortedRange:NSMakeRange(0, self.backingMessages.count) options:NSBinarySearchingInsertionIndex usingComparator:^NSComparisonResult(Message* _Nonnull obj1, Message* _Nonnull obj2) {
 return [obj1.fullTimestamp compare:obj2.fullTimestamp];
 }];
 self.backingMessages[insertionPoint] = message;
}

Some observations:

• The new messages being added are known to be sorted
• The messages being added to are initially sorted, and so will also be sorted every time new messages are added.

Doing some back-of-the-napkin analysis...

n = length of existing message array 
m = length of new message array 
implementation 1: O(m) + O((n+m)log(n+m)) 
implementation 2: O(mlog(n+m)) + O(m) <- for the shifting that I assume happens upon insertion

My gut says that implementation 2 would be faster by a hair, depending on how the shifting works. All of this being said, I'm assuming that Apple ends up doing some crazy polymorphic implementation for sorting depending on the data, so implementation 1 might end up being faster. I'm probably overthinking this since the amount of data I'm expecting is so small, but I'm still curious about what might theoretically be faster.

Answer 1

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.

• Chris: Good catch, I'll review the code and see if that observation fits with the data I'm getting back.