Sort direction (asc, desc) in Rest API - Time & Space Complexity

Time Complexity: Sort direction (asc, desc)

O(n log n)

Understanding Time Complexity

When sorting data in ascending or descending order, it is important to understand how the time taken grows as the data size increases.

We want to know how the sorting operation's cost changes when we have more items to sort.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

GET /items?sort=asc

// Server fetches all items
// Then sorts items by price ascending or descending
const sortedItems = items.sort((a, b) => {
  if (sortDirection === 'asc') return a.price - b.price;
  else return b.price - a.price;
});
return sortedItems;
    

This code sorts a list of items by their price in either ascending or descending order based on the request.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The sorting algorithm compares pairs of items multiple times.
• How many times: The number of comparisons grows as the list size increases, usually more than once per item.

How Execution Grows With Input

As the number of items grows, the sorting takes more time because it must compare many pairs.

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

Pattern observation: The number of operations grows faster than the number of items, roughly as n log n.

Final Time Complexity

Time Complexity: O(n log n)

This means that as the list grows, the time to sort grows a bit faster than the list size but much slower than checking every pair.

Common Mistake

[X] Wrong: "Sorting ascending is faster than sorting descending because it feels simpler."

[OK] Correct: Both ascending and descending sorting use the same process and take about the same time regardless of direction.

Interview Connect

Understanding how sorting time grows helps you explain performance in real apps where users want data sorted quickly.

Self-Check

"What if the items were already sorted? How would that affect the time complexity of sorting in ascending or descending order?"