Sorting with sort parameter in Rest API - Time & Space Complexity

Time Complexity: Sorting with sort parameter

O(n log n)

Understanding Time Complexity

When using a sort parameter in a REST API, the server arranges data before sending it. Understanding how this sorting affects time helps us know how fast the API responds as data grows.

We want to see how the time to sort changes when the number of items increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

GET /items?sort=price

// Server receives request
// Fetch all items from database
// Sort items by price
// Return sorted list
    

This code fetches a list of items and sorts them by price before sending the response.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sorting the list of items by price.
• How many times: The sorting algorithm compares and rearranges items multiple times depending on the number of items.

How Execution Grows With Input

As the number of items grows, the sorting work grows faster than just counting items. For example:

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

Pattern observation: When the list size grows, the number of operations grows faster than the list size itself, roughly multiplying by n log n.

Final Time Complexity

Time Complexity: O(n log n)

This means sorting takes more time as the list grows, but not as fast as checking every pair; it grows in a balanced way with the number of items.

Common Mistake

[X] Wrong: "Sorting with a sort parameter takes the same time no matter how many items there are."

[OK] Correct: Sorting needs to compare and arrange items, so more items mean more work and longer time.

Interview Connect

Knowing how sorting scales helps you explain API performance clearly. It shows you understand how data size affects response time, a useful skill in real projects.

Self-Check

"What if the API returned only the top 10 sorted items instead of all? How would the time complexity change?"

Practice

1. What does the sort parameter do in a REST API request?

easy

A. It filters data based on a condition.

B. It controls the order in which data is returned.

C. It limits the number of results returned.

D. It changes the data format to XML.

Solution

1. Step 1: Understand the purpose of the sort parameter

   The sort parameter is used to arrange the returned data in a specific order.

2. Step 2: Differentiate from other parameters

   Filtering limits data, limiting controls count, and format changes output type, but sorting changes order.

3. Final Answer:

   It controls the order in which data is returned. -> Option B

4. Quick Check:

   Sort parameter = controls order [OK]

Hint: Sort means order, not filter or limit [OK]

Common Mistakes:

• Confusing sort with filter
• Thinking sort limits results
• Assuming sort changes data format

2. Which of the following is the correct way to sort results by the field price in descending order using the sort parameter?

easy

A. sort=desc(price)

B. sort=price-

C. sort=-price

D. sort=price_desc

Solution

1. Step 1: Identify descending order syntax

   In REST APIs, prefixing the field with a minus sign - sorts in descending order.

2. Step 2: Match the correct syntax

   Only sort=-price correctly uses the minus prefix before the field name.

3. Final Answer:

   sort=-price -> Option C

4. Quick Check:

   Minus before field = descending sort [OK]

Hint: Use '-' before field for descending sort [OK]

Common Mistakes:

• Placing '-' after the field name
• Using function-like syntax incorrectly
• Appending '_desc' instead of '-' prefix

3. Given the API request /products?sort=-rating, what will be the order of the returned products?

medium

A. Products sorted by rating from highest to lowest.

B. Products sorted alphabetically by name.

C. Products sorted by rating from lowest to highest.

D. Products sorted by price from lowest to highest.

Solution

1. Step 1: Analyze the sort parameter

   The parameter sort=-rating means sort by the field rating in descending order.

2. Step 2: Determine the order of sorting

   Descending order means highest values first, so products with highest rating come first.

3. Final Answer:

   Products sorted by rating from highest to lowest. -> Option A

4. Quick Check:

   Minus prefix = descending order [OK]

Hint: Minus means descending, so highest values first [OK]

Common Mistakes:

• Assuming minus means ascending
• Confusing rating with price or name
• Ignoring the minus sign

4. You wrote the API request /users?sort=name- to sort users by name descending, but it returns an error. What is the problem?

medium

A. The minus sign should be before the field name, not after.

B. The field name name is invalid for sorting.

C. The sort parameter cannot be used with strings.

D. You need to use order=name_desc instead.

Solution

1. Step 1: Check the position of the minus sign

   The correct syntax places the minus sign before the field name to indicate descending order.

2. Step 2: Identify the error cause

   Using name- places the minus after the field, which is invalid and causes an error.

3. Final Answer:

   The minus sign should be before the field name, not after. -> Option A

4. Quick Check:

   Minus must prefix field for descending [OK]

Hint: Minus after field causes error; put it before [OK]

Common Mistakes:

• Placing minus after field name
• Assuming sort can't be used on strings
• Using wrong parameter like 'order'

5. You want to get a list of blog posts sorted first by date descending, then by title ascending. Which sort parameter should you use?

hard

A. sort=-title,date

B. sort=date,-title

C. sort=title,-date

D. sort=-date,title

Solution

1. Step 1: Understand multi-field sorting syntax

   Multiple fields are separated by commas; order matters for sorting priority.

2. Step 2: Apply descending and ascending correctly

   Use -date for descending date, and title without minus for ascending title.

3. Step 3: Combine fields in correct order

   First sort by date descending, then by title ascending means sort=-date,title.

4. Final Answer:

   sort=-date,title -> Option D

5. Quick Check:

   Minus before date, comma, then title ascending [OK]

Hint: List fields comma-separated; minus means descending [OK]

Common Mistakes:

• Reversing field order
• Putting minus on ascending field
• Using wrong separators like semicolon