ORDER BY with ASC and DESC in SQL - Time & Space Complexity

Time Complexity: ORDER BY with ASC and DESC

O(n log n)

Understanding Time Complexity

When we sort data using ORDER BY, the database rearranges rows based on column values.

We want to know how the time to sort grows as the data size grows.

Scenario Under Consideration

Analyze the time complexity of this SQL query:

SELECT *
FROM employees
ORDER BY salary DESC, name ASC;
    

This query sorts employees first by salary from highest to lowest, then by name alphabetically.

Identify Repeating Operations

Sorting involves comparing rows multiple times to order them.

• Primary operation: Comparing and swapping rows during sorting.
• How many times: Depends on sorting algorithm, but many comparisons grow with number of rows.

How Execution Grows With Input

Sorting takes more time as rows increase, but not just adding up; it grows faster.

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

Pattern observation: Operations grow faster than the number of rows, roughly multiplying by n log n.

Final Time Complexity

Time Complexity: O(n log n)

This means sorting takes a bit more than just looking at each row once; it grows a little faster as data grows.

Common Mistake

[X] Wrong: "Sorting rows takes the same time no matter how many rows there are."

[OK] Correct: Sorting compares many pairs of rows, so more rows mean many more comparisons, not just a simple increase.

Interview Connect

Understanding how sorting time grows helps you explain database performance clearly and confidently.

Self-Check

"What if the data was already sorted? How would that affect the time complexity of ORDER BY?"