ORDER BY multiple columns in SQL - Time & Space Complexity

Time Complexity: ORDER BY multiple columns

O(n log n)

Understanding Time Complexity

When sorting data by more than one column, it is important to understand how the sorting time changes as the data grows.

We want to know how the sorting work increases when we order by multiple columns instead of just one.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT *
FROM employees
ORDER BY department, salary DESC;
    

This query sorts employees first by their department, then by salary in descending order within each department.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sorting the entire list of rows based on multiple columns.
• How many times: The sorting algorithm compares and rearranges rows multiple times, depending on the number of rows.

How Execution Grows With Input

Sorting time grows as the number of rows increases, because more rows mean more comparisons and swaps.

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 rows grows, the sorting work grows faster than the number of rows, roughly multiplying by a bit more than the number itself.

Final Time Complexity

Time Complexity: O(n log n)

This means sorting takes more time as the list grows, but it grows in a way that is faster than simple counting but slower than multiplying by itself.

Common Mistake

[X] Wrong: "Ordering by multiple columns makes sorting take twice as long as ordering by one column."

[OK] Correct: Sorting time depends mostly on the number of rows, not the number of columns sorted. Adding more columns to sort adds only a small extra cost per comparison, not doubling the whole sorting time.

Interview Connect

Understanding how sorting scales with data size and multiple columns helps you explain query performance clearly and confidently in real situations.

Self-Check

"What if we added an index on the columns used in ORDER BY? How would the time complexity change?"