ORDER BY multiple columns in MySQL - 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 ASC, salary DESC;
    

This query sorts employees first by their department in ascending order, 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 takes more work as the number of rows grows, but adding more columns to sort by does not multiply the work by much.

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

Pattern observation: The number of operations grows a bit faster than the number of rows, but adding more columns to sort by only adds small extra work per comparison.

Final Time Complexity

Time Complexity: O(n log n)

This means the sorting work grows a little more than linearly with the number of rows, even when sorting by multiple columns.

Common Mistake

[X] Wrong: "Sorting by two columns takes twice as long as sorting by one column."

[OK] Correct: Sorting compares rows multiple times anyway, so adding a second column only adds a small extra step per comparison, not doubling the total work.

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