What sorting alogrithm is used by mongodb's sort and nested array sort?

Question

I am experimenting with MongoDB's sort performance to decide whether or not to store a user's location history {ts: DATE(), location: "loc"} (maxHistorySize=100) within the user object or in a separate collection.

My goal is to achieve better TPS. It's expected to have a lot more writes than reads.

The major concern I have right now is the performance of sorting (which I will need for querying and housekeeping, also while inserting(create index)).

When stored within, the write query would be something like this. My concern is how quickly it can finish the sort. Since the $sort run every time an insertion takes place, the array would be largely sorted already. I am wonder whether the sort has a runtime of O(log(n)) or O(nlog(n))

        update: {
          $setOnInsert: {userId: 'userId'},
          $push: {
            locations: {
              $each: [{location: 'location', ts: new Date()}],
              $slice: -100,
              $sort: {ts: 1}
            }
          },

When stored separately, I would have to create an index on ts. Since MongoDB uses B-tree to create an index, I am guessing the overhead is just O(log(n)). The drawback is that it uses extra spaces.

I am not sure where, to begin with, any recommendations is appreciated. Thanks

Answer 1

MongoDB uses std::sort (called from sortChildren called from PushNode::performPush.

I believe std::sort is O(nlog(n)).