Sorting by multiple fields in MongoDB - Time & Space Complexity

Time Complexity: Sorting by multiple fields

O(n log n)

Understanding Time Complexity

When sorting data by more than one field in MongoDB, the time it takes depends on how many items you have and how the database organizes them.

We want to understand how the sorting time grows as the number of documents increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

db.collection.find().sort({ age: 1, name: -1 })

This code sorts documents first by the age field in ascending order, then by name in descending order.

Identify Repeating Operations

• Primary operation: Comparing and ordering each document based on the two fields.
• How many times: Each document is compared multiple times during sorting, roughly proportional to the number of documents.

How Execution Grows With Input

Sorting time grows faster than just looking at each item once because items must be compared and rearranged.

Input Size (n)	Approx. Operations
10	About 30 to 40 comparisons
100	About 700 to 800 comparisons
1000	About 10,000 to 12,000 comparisons

Pattern observation: As the number of documents grows, the number of comparisons grows faster than the number of documents, but not as fast as every pair compared directly.

Final Time Complexity

Time Complexity: O(n log n)

This means sorting takes more time as you add more documents, growing a bit faster than just going through each one once.

Common Mistake

[X] Wrong: "Sorting by multiple fields is just as fast as sorting by one field because it's still one sort operation."

[OK] Correct: Sorting by multiple fields means the database compares more details for each pair, so it takes more time than sorting by a single field.

Interview Connect

Understanding how sorting time grows helps you explain how databases handle ordering large data sets efficiently, a useful skill in many real projects.

Self-Check

"What if we added an index on the fields used for sorting? How would the time complexity change?"