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?"

Practice

1. What does sorting by multiple fields in MongoDB allow you to do?

easy

A. Organize data by more than one field in a specific order

B. Delete multiple fields from documents

C. Create new fields based on existing ones

D. Filter documents by multiple conditions

Solution

1. Step 1: Understand sorting purpose

   Sorting arranges documents in order based on field values.

2. Step 2: Recognize multiple fields effect

   Sorting by multiple fields means ordering by the first field, then by the second if the first is equal, and so on.

3. Final Answer:

   Organize data by more than one field in a specific order -> Option A

4. Quick Check:

   Sorting by multiple fields = Organize data by multiple fields [OK]

Hint: Sorting multiple fields orders by priority fields [OK]

Common Mistakes:

• Confusing sorting with filtering
• Thinking sorting creates or deletes fields
• Assuming sorting only works on one field

2. Which of the following is the correct syntax to sort documents by age ascending and name descending in MongoDB?

easy

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

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

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

D. db.collection.find().sort({age: 'asc', name: 'desc'})

Solution

1. Step 1: Recall sort syntax

   MongoDB uses 1 for ascending and -1 for descending order in sort objects.

2. Step 2: Match fields and order

   Sorting by age ascending (1) and name descending (-1) matches db.collection.find().sort({age: 1, name: -1}).

3. Final Answer:

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

4. Quick Check:

   age:1, name:-1 syntax = db.collection.find().sort({age: 1, name: -1}) [OK]

Hint: Use 1 for ascending, -1 for descending in sort object [OK]

Common Mistakes:

• Using strings like 'asc' or 'desc' instead of 1 or -1
• Mixing order of fields incorrectly
• Using wrong signs for ascending/descending

3. Given the collection documents:

{"name": "Alice", "age": 30, "score": 85}
{"name": "Bob", "age": 25, "score": 90}
{"name": "Alice", "age": 30, "score": 95}

What is the order of documents after running db.collection.find().sort({name: 1, age: -1, score: 1})?

medium

A. [{name: "Alice", age: 30, score: 85}, {name: "Bob", age: 25, score: 90}, {name: "Alice", age: 30, score: 95}]

B. [{name: "Alice", age: 30, score: 95}, {name: "Alice", age: 30, score: 85}, {name: "Bob", age: 25, score: 90}]

C. [{name: "Bob", age: 25, score: 90}, {name: "Alice", age: 30, score: 85}, {name: "Alice", age: 30, score: 95}]

D. [{name: "Alice", age: 30, score: 85}, {name: "Alice", age: 30, score: 95}, {name: "Bob", age: 25, score: 90}]

Solution

1. Step 1: Sort by name ascending

   Names sorted ascending: "Alice" before "Bob".

2. Step 2: Sort by age descending within same name

   Both "Alice" have age 30, so order stays same.

3. Step 3: Sort by score ascending within same name and age

   Scores 85 then 95 for "Alice".

4. Final Answer:

   [{name: "Alice", age: 30, score: 85}, {name: "Alice", age: 30, score: 95}, {name: "Bob", age: 25, score: 90}] -> Option D

5. Quick Check:

   Sort by name↑, age↓, score↑ = [{name: "Alice", age: 30, score: 85}, {name: "Alice", age: 30, score: 95}, {name: "Bob", age: 25, score: 90}] [OK]

Hint: Sort priority follows field order in sort object [OK]

Common Mistakes:

• Ignoring order of fields in sort
• Mixing ascending and descending incorrectly
• Assuming score sorts descending by default

4. Identify the error in this MongoDB sort query:

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

medium

A. Using 2 instead of -1 or 1 for sorting order

B. Missing parentheses after find()

C. Using curly braces instead of square brackets

D. Sorting fields must be strings, not numbers

Solution

1. Step 1: Check valid sort values

   MongoDB accepts only 1 (ascending) or -1 (descending) as sort values.

2. Step 2: Identify invalid value

   Value 2 is invalid and causes syntax error.

3. Final Answer:

   Using 2 instead of -1 or 1 for sorting order -> Option A

4. Quick Check:

   Sort values must be 1 or -1 [OK]

Hint: Sort values must be 1 or -1, never other numbers [OK]

Common Mistakes:

• Using numbers other than 1 or -1
• Confusing sort object syntax
• Assuming 2 means descending

5. You want to sort a collection by department ascending, then by salary descending, but only for employees with the same department. Which MongoDB query correctly achieves this?

hard

A. db.employees.find().sort({salary: -1, department: 1})

B. db.employees.find().sort({department: 1, salary: -1})

C. db.employees.find().sort({department: -1, salary: 1})

D. db.employees.find().sort({salary: 1, department: -1})

Solution

1. Step 1: Understand sorting priority

   Sorting by department ascending means all employees grouped by department alphabetically.

2. Step 2: Sort salary descending within each department

   Within each department group, employees are ordered by salary from highest to lowest.

3. Step 3: Match correct sort order

   db.employees.find().sort({department: 1, salary: -1}) matches department:1 (ascending) and salary:-1 (descending).

4. Final Answer:

   db.employees.find().sort({department: 1, salary: -1}) -> Option B

5. Quick Check:

   Sort by department↑ then salary↓ = db.employees.find().sort({department: 1, salary: -1}) [OK]

Hint: Order fields in sort by priority, use 1 or -1 for direction [OK]

Common Mistakes:

• Reversing field order in sort object
• Using wrong sort directions
• Assuming sorting salary first groups by salary only